柚子快報激活碼778899分享：算法 【數(shù)據(jù)結(jié)構(gòu)初階】復(fù)雜度

http://yzkb.51969.com/

目錄

一、時間復(fù)雜度

????????1、時間復(fù)雜度的概念

? ??????2、大O的漸進表示法

????????3、常見的時間復(fù)雜度計算舉例

二、空間復(fù)雜度

????????1、空間復(fù)雜度的概念

????????2、常見的空間復(fù)雜度計算舉例

三、常見復(fù)雜度對比

正文開始——

前言

一個算法，并非越簡潔越好，那該如何衡量一個算法的好壞呢？看其復(fù)雜度。復(fù)雜度又分為時間復(fù)雜度和空間復(fù)雜度。

一、時間復(fù)雜度?

1.? 時間復(fù)雜度的概念?

在計算機科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運行時間。一個算法執(zhí)行程序所消耗的時間，從理論上說，是不能算出來的，只有上機測試才能得知，于是我們有了時間復(fù)雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù)雜度。

void Func1(int N)

{

int count = 0;

for (int i = 0; i < N ; ++ i)

{

for (int j = 0; j < N ; ++ j)

{

++count;

}

for (int k = 0; k < 2 * N ; ++ k)

{

++count;

}

int M = 10;

while (M--)

{

++count;

}

printf("%d\n",count);

}

Func1執(zhí)行的基本次數(shù)：N^2+2*N+10

實際計算時間復(fù)雜度，我們不一定要精確計算執(zhí)行次數(shù)，只需要計算大概的執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。

2.? 大O的漸進表示法?

大O符號：是用于描述函數(shù)漸進行為的數(shù)學(xué)符號。

推導(dǎo)大O階方法：

用常數(shù)1取代運行時間中的所有加法常數(shù)。在修改后的運行次數(shù)函數(shù)中，只保留最高階項。如果最高階項存在且不為1，則去除與這個項相乘的常數(shù)。得到的結(jié)果就是大O階。

so Func1的時間復(fù)雜度為：O（N^2）。通過上面我們發(fā)現(xiàn)大O的漸進法去掉了那些對結(jié)果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。

另外有些算法的時間復(fù)雜度存在最好、平均和最壞情況：

最壞情況：任意輸入規(guī)模的最大運行次數(shù)（上界）

平均情況：任意輸入規(guī)模的期望運行次數(shù)

最好情況：任意輸入規(guī)模的最小運行次數(shù)（下界）

例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x

最壞情況：N次找到

平均情況：N/2次找到

最好情況：1次找到

在實際中一般情況關(guān)注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)x的時間復(fù)雜度為O（N）。

3.? 常見的時間復(fù)雜度計算舉例?

實例1：

//計算Func2的時間復(fù)雜度

void Func2(int N)

{

int count=0;

for(int k=0;k<2*N;k++)

{

++count;

}

int M=10;

while(M--)

{

++count;

}

printf("%d\n",count);

}

【解析】Func2執(zhí)行的基本次數(shù)：N*2+10 ，所以其時間復(fù)雜度為：O（N）。

實例2：

//計算Func3的時間復(fù)雜度

void Func3(int N,int M)

{

int count=0;

for(int k=0;k

{

++count；

}

for(int k=0;k

{

++count；

}

printf("%d\n",count);

}

【解析】Func3執(zhí)行的基本次數(shù)：M+ N，有兩個未知數(shù)M，N，時間復(fù)雜度：O（M+N）。

實例3：

//計算Func4的時間復(fù)雜度

void Func4(int N)

{

int count=0;

for(int k=0;k<100;++k)

{

++count;

}

printf("%d\n",count);

}

【解析】Func4執(zhí)行的基本次數(shù)：100，對于常數(shù)一律用O（1）。

實例4：

//計算strchr的時間復(fù)雜度

const char* strchr (const char* str,int character);

【解析】基本操作最好情況執(zhí)行1次，最壞N次，時間復(fù)雜度一般看最壞，時間復(fù)雜度為O（N）。

實例5：

//計算BubbleSort的時間復(fù)雜度

void BubbleSort(int* a,int n)

{

assert(a);

for(size_t end=n;end>0;--end)

{

int exchange=0;

for(size_t i=1;i

{

if(a[i-1]>a[i])

{

Swap(&a[i-1],&a[i]);

exchange=1;

}

}

if(exchange==0)

break;

}

}

【解析】基本操作最好情況執(zhí)行N次，最壞執(zhí)行（N*（N+1））/2次，所以時間復(fù)雜度為O（N^2）.

實例6：

int BinarySearch(int* a, int n, int x)

{

assert(a);

int begin = 0;

int end = n-1;

// [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號

while (begin <= end)

{

int mid = begin + ((end-begin)>>1);

if (a[mid] < x)

begin = mid+1;

else if (a[mid] > x)

end = mid-1;

else

return mid;

}

return -1;

}

【解析】基本操作最好執(zhí)行1次，最壞O（logN）次，時間復(fù)雜度為O（logN）。ps：logN在算法分析中表示底數(shù)為2，對數(shù)為N。

實例7：

// 計算階乘遞歸Fac的時間復(fù)雜度

long long Fac(size_t N)

{

if(0 == N)

return 1;

return Fac(N-1)*N;

}

【解析】遞歸了N次，時間復(fù)雜度為O（N）。

實例8：

// 計算斐波那契遞歸Fib的時間復(fù)雜度

long long Fib(size_t N)

{

if(N < 3)

return 1;

return Fib(N-1) + Fib(N-2)

}

【解析】時間復(fù)雜度為O（2^N）。

二、空間復(fù)雜度?

1.? 空間復(fù)雜度的概念?

空間復(fù)雜度也是一個數(shù)學(xué)表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度。

空間復(fù)雜度不是程序占用了多少bytes的空間，因為這個也沒有太大意義，所以空間復(fù)雜度算的是變量的個數(shù)?？臻g復(fù)雜度計算規(guī)則與時間復(fù)雜度相似，也是用大O漸進表示法。

【注意】函數(shù)運行時所需要的棧空間（存儲函數(shù)、局部變量、一些寄存器信息等）在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運行時候?顯示申請的額外空間?來確定。

2.? 常見空間復(fù)雜度計算舉例?

實例1：

// 計算BubbleSort的空間復(fù)雜度？

void BubbleSort(int* a, int n)

{

assert(a);

for (size_t end = n; end > 0; --end)

{

int exchange = 0;

for (size_t i = 1; i < end; ++i)

{

if (a[i-1] > a[i])

{

Swap(&a[i-1], &a[i]);

exchange = 1;

}

}

if (exchange == 0)

break;

}

}

【解析】 在函數(shù)運行過程中申請常數(shù)個額外空間，所以空間復(fù)雜度為O（1）。

實例2：

// 計算Fibonacci的空間復(fù)雜度

// 返回斐波那契數(shù)列的前n項

long long* Fibonacci(size_t n)

{

if(n==0)

return NULL;

long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));

fibArray[0] = 0;

fibArray[1] = 1;

for (int i = 2; i <= n ; ++i)

{

fibArray[i] = fibArray[i - 1] + fibArray [i - 2];

}

return fibArray;

}

【解析】 動態(tài)開辟了N個空間，所以空間復(fù)雜度為O（N）。

實例3：

// 計算階乘遞歸Fac的空間復(fù)雜度

long long Fac(size_t N)

{

if(N == 0)

return 1;

return Fac(N-1)*N;

}

【解析】遞歸調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)個空間。空間復(fù)雜度為O（N）。

三、常見復(fù)雜度對比?

完——

——————————————————? ?綠色? ?——————————————————

綠色_陳雪凝_高音質(zhì)在線試聽_綠色歌詞|歌曲下載_酷狗音樂酷狗音樂為您提供由陳雪凝演唱的高清音質(zhì)無損綠色mp3在線聽,聽綠色,只來酷狗音樂!https://t4.kugou.com/song.html?id=7dQq7a4CPV2

?你是否也期待來一場說走就走的旅行——

?期待我們下一次的相遇——

柚子快報激活碼778899分享：算法 【數(shù)據(jù)結(jié)構(gòu)初階】復(fù)雜度

http://yzkb.51969.com/

參考閱讀