第C語言詳細(xì)解析時(shí)間復(fù)雜度與空間復(fù)雜度目錄一、概念1.1、算法效率1.2、時(shí)間復(fù)雜度1.3、空間復(fù)雜度二、計(jì)算2.1、大O的漸進(jìn)表示法2.2、時(shí)間復(fù)雜度計(jì)算2.3、空間復(fù)雜度計(jì)算三、有復(fù)雜度要求的習(xí)題

一、概念

1.1、算法效率

如何衡量一個(gè)算法的好壞比如對(duì)于以下斐波那契數(shù)列：

longlongFib(intN)

if(N3)

return1;

returnFib(N-1)+Fib(N-2);

}

斐波那契數(shù)列用遞歸實(shí)現(xiàn)方式非常簡(jiǎn)潔，但簡(jiǎn)潔一定好嗎？那該如何衡量其好與壞呢？在學(xué)完時(shí)間復(fù)雜度會(huì)為您揭曉。

算法效率分析分為兩種：第一種是時(shí)間效率，第二種是空間效率。時(shí)間效率被稱為時(shí)間復(fù)雜度，而空間效率被稱作空間復(fù)雜度。時(shí)間復(fù)雜度主要衡量的是一個(gè)算法的運(yùn)行速度，而空間復(fù)雜度主要衡量一個(gè)算法所需要的額外空間，在計(jì)算機(jī)發(fā)展的早期，計(jì)算機(jī)的存儲(chǔ)容量很小。所以對(duì)空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展，計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度

1.2、時(shí)間復(fù)雜度

一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。

1.3、空間復(fù)雜度

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度?？臻g復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)?？臻g復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用大O漸進(jìn)表示法。

二、計(jì)算

2.1、大O的漸進(jìn)表示法

先看一串代碼：

//請(qǐng)計(jì)算一下Func1基本操作執(zhí)行了多少次？

voidFunc1(intN)

intcount=0;

for(inti=0;i++i)

for(intj=0;j++j)

++count;

for(intk=0;k2*N;++k)

++count;

intM=10;

while(M--)

++count;

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

}

算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。顯而易見，這里Func1執(zhí)行的最準(zhǔn)確操作次數(shù)：F(N)=N*N+2*N+10

例如F(10)=130、F(100)=10210、F(1000)=1002010

按理來說此題的時(shí)間復(fù)雜度就是上述的公式，其實(shí)不然。時(shí)間復(fù)雜度是一個(gè)估算，是去看表達(dá)式中影響最大的那一項(xiàng)。此題隨著N的增大，這個(gè)表達(dá)式中N^2對(duì)結(jié)果的影響是最大的

實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次

數(shù)，那么這里我們使用大O的漸進(jìn)表示法。，因而上題的時(shí)間復(fù)雜度為O(N^2)

大O符號(hào)（BigOnotation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。

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

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

通過上面我們會(huì)發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對(duì)結(jié)果影響不大的項(xiàng)，簡(jiǎn)潔明了的表示出了執(zhí)行次數(shù)。另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：

最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)

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

最好情況：1次找到最壞情況：N次找到平均情況：N/2次找到

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

注意：遞歸算法時(shí)間復(fù)雜度計(jì)算

每次函數(shù)調(diào)用是O(1)，那么就看他的遞歸次數(shù)每次函數(shù)調(diào)用不是O(1)，那么就看他的遞歸調(diào)用中次數(shù)的累加

2.2、時(shí)間復(fù)雜度計(jì)算

例題：

例一：

//計(jì)算Func2的時(shí)間復(fù)雜度？

voidFunc2(intN)

intcount=0;

for(intk=0;k2*N;++k)

++count;

intM=10;

while(M--)

++count;

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

}

答案：O(N)

解析：此題中最準(zhǔn)確的次數(shù)為2*N+10，而其中影響最大的是N，可能有人覺著是2*N，但隨著N的不斷增大，2對(duì)結(jié)果的影響不是很大，況且要符合上述第三條規(guī)則：如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。所以把2去除掉，因而時(shí)間復(fù)雜度為O(N)

例二：

//計(jì)算Func3的時(shí)間復(fù)雜度？

voidFunc3(intN,intM)

intcount=0;

for(intk=0;k++k)

++count;

for(intk=0;k++k)

++count;

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

}

答案：O(M+N)

解析：因?yàn)镸和N都是未知數(shù)，所以N和M都要帶著，但是如果題目明確M遠(yuǎn)大于N，那么時(shí)間復(fù)雜度就是O(M)，如果M和N差不多大，那么時(shí)間復(fù)雜度就是O(M)或O(N)

例三：

//計(jì)算Func4的時(shí)間復(fù)雜度？

voidFunc4(intN)

intcount=0;

for(intk=0;k100;++k)

++count;

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

}

答案：O(1)

解析：這里最準(zhǔn)確的次數(shù)是100，但是要符合大O的漸進(jìn)表示法的規(guī)則，用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。所以時(shí)間復(fù)雜度就是O(1)

例四：

//計(jì)算strchr的時(shí)間復(fù)雜度？

constchar*strchr(constchar*str,charcharacter)

while(*str!='\0')

if(*str==character)

returnstr;

++str;

returnNULL;

}

答案：O(N)

解析：此題就要分情況了，這里假設(shè)字符串為abcdefghijklmn，如果目標(biāo)字符找的是g，則需要執(zhí)行N/2次，如果找到是a，則需要執(zhí)行1次，如果找n，則N次，所以要分情況，這里就出現(xiàn)了有些算法的時(shí)間復(fù)雜度存在最好O(1)、平均O(N/2)和最壞O(N)情況，但是在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況，所以此題時(shí)間復(fù)雜度為O(N)

例五：

//計(jì)算BubbleSort的時(shí)間復(fù)雜度？

voidBubbleSort(int*a,intn)

assert(a);

for(size_tend=n;end--end)

intexchange=0;

for(size_ti=1;iend;++i)

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

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

exchange=1;

if(exchange==0)

break;

}

答案：O(N^2)

解析：此段代碼考到的是冒泡排序。第一趟的冒泡排序走了N次，第二趟走了N-1次，第三趟N-2，最后就是1，次規(guī)律正合等差數(shù)列，求和即為(N+1)*N/2，當(dāng)然這個(gè)是最準(zhǔn)確的，這里還要找對(duì)結(jié)果影響最大的那一項(xiàng)，即N^2，所以時(shí)間復(fù)雜度是O(N^2)

例六：

//計(jì)算BinarySearch的時(shí)間復(fù)雜度？

intBinarySearch(int*a,intn,intx)

assert(a);

intbegin=0;

intend=n;

while(beginend)

intmid=begin+((end-begin)1);

if(a[mid]x)

begin=mid+1;

elseif(a[mid]x)

end=mid;

else

returnmid;

return-1;

}

答案：O(logN)

解析：此題很明顯考到的是二分查找。假設(shè)數(shù)組長(zhǎng)度為N，且找了X次，則1*2*2*2*2**2=N，即為2^X=N，則X等于log以2為底N的對(duì)數(shù)，而算法的復(fù)雜度計(jì)算，喜歡省略簡(jiǎn)寫成logN，因?yàn)楹芏嗟胤讲缓脤懙讛?shù)，所以此題時(shí)間復(fù)雜度為O(logN)

例七：

//計(jì)算階乘遞歸Factorial的時(shí)間復(fù)雜度？

longlongFactorial(size_tN)

returnN2N:Factorial(N-1)*N;

}

答案：O(N)

解析：如果N為10

例八：

longlongFib(intN)

if(N3)

return1;

returnFib(N-1)+Fib(N-2);

}

這串代碼是上文最開始呈現(xiàn)的代碼，代碼風(fēng)格十分簡(jiǎn)單，短短幾行便可完成斐波那契數(shù)列的計(jì)算，可看似這么簡(jiǎn)潔的代碼真的好嗎？先來計(jì)算一下時(shí)間復(fù)雜度：

答案：O(2^N)

解析：

有上圖可以得知，第一行執(zhí)行1次，第二行執(zhí)行2^1次，第三行執(zhí)行2^2次，以此類推，是個(gè)等比數(shù)列，累計(jì)算下來再根據(jù)大O階表示法的規(guī)則得知，此斐波那契數(shù)列的時(shí)間復(fù)雜度為O(2^N)。

但是，根據(jù)2^N這個(gè)時(shí)間復(fù)雜度是個(gè)非常大的數(shù)字，當(dāng)n=10時(shí)，在VS環(huán)境下很快容易得到答案，但是當(dāng)n稍微再大一點(diǎn)比如說是50，就要等上很長(zhǎng)一段時(shí)間才能將結(jié)果算出來，由此可見，簡(jiǎn)潔的代碼不一定是最優(yōu)的代碼。

常見時(shí)間復(fù)雜度：O(N^2)、O(N)、O(logN)、O(1)

復(fù)雜度對(duì)比：

2.3、空間復(fù)雜度計(jì)算

空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度?？臻g復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)?？臻g復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用大O漸進(jìn)表示法。注意：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來確定。

例題

例一：

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

voidBubbleSort(int*a,intn)

assert(a);

for(size_tend=n;end--end)

intexchange=0;

for(size_ti=1;iend;++i)

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

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

exchange=1;

if(exchange==0)

break;

}

答案：O(1)

解析：這里其實(shí)總共開辟了三個(gè)空間，分別為end、exchange、i，既然是常數(shù)個(gè)變量，那么空間復(fù)雜度就是O(1)，空間復(fù)雜度算的是申請(qǐng)的額外空間，所以跟上面的int*a和intn沒有關(guān)系?？赡苡腥擞X著這是個(gè)for循環(huán)，exchange應(yīng)該開辟n次，其實(shí)每次循環(huán)進(jìn)來，exchange都會(huì)重新開辟，結(jié)束一次循環(huán)exchange銷毀，以此類推，exchange始終是同一個(gè)空間。

而什么時(shí)候會(huì)出現(xiàn)O(n)呢？

1、malloc一個(gè)數(shù)組

int*a=(int*)malloc(sizeof(int)*numsSize);//O(N)

此情況的前提是numsSize必須是個(gè)未知的數(shù)字，如果是具體數(shù)字，那么空間復(fù)雜度依舊是O(1)

2、變長(zhǎng)數(shù)組

inta[numsSize];//numsSize未知，O(N)

例二：

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

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

longlong*Fibonacci(size_tn)

if(n==0)

returnNULL;

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

fibArray[0]=0;

fibArray[1]=1;

for(inti=2;i++i)

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

returnfibArray;

}

答案：O(N+1)

解析：這里看到了malloc開辟了n+1個(gè)大小為longlong類型的數(shù)組，看到這就不需要再過多計(jì)較后續(xù)創(chuàng)建了幾個(gè)變量，因?yàn)榭臻g復(fù)雜度是估算，所以直接就是O(N)

例三：

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

longlongFac(size_tN)

if(N==0)

return1;

returnFac(N-1)*N;

}

答案：O(1)

解析：這里遞歸函數(shù)是要建立棧幀的，而建立棧幀的個(gè)數(shù)為N個(gè)，每個(gè)棧幀的變量都是常數(shù)個(gè)，N個(gè)即空間復(fù)雜度為O(N)

例四：

//計(jì)算斐波那契遞歸Fib的空間復(fù)雜度？

longlongFib(size_tN)

if(N3)

return1;

returnFib(N-1)+Fib(N-2);

}

答案：O(N)

解析：時(shí)間一去不復(fù)返，是累積的，空間回收以后是可以重復(fù)利用的。當(dāng)遞歸到Fib(3)的時(shí)候，此時(shí)調(diào)用Fib(2)和Fib(1)，調(diào)到Fib(2)就可以返回了，此時(shí)Fib(2)的棧幀就銷毀了，此時(shí)再調(diào)用的Fib(1)和Fib(2)用的就是同一塊空間，同理Fib(N-1)總共建立了N-1個(gè)棧幀，同理再調(diào)用Fib(N-2)和剛才Fib(N-1)使用的是同一塊空間，充分說明了時(shí)間一去不復(fù)返，是累積的，空間回收以后是可以重復(fù)利用的。

三、有復(fù)雜度要求的習(xí)題

題一：（消失的數(shù)字）

鏈接：/problems/missing-number-lcci/

此題就明確了一個(gè)要求：想辦法在O(n)的時(shí)間內(nèi)完成，本題將提供兩種有效且可行的方法，正文開始：

法一：相加-相加

思想：

此題是在一串連續(xù)的整數(shù)中缺了一個(gè)數(shù)，那我們就把理應(yīng)有的整數(shù)個(gè)數(shù)依次相加再減去原數(shù)組中缺一個(gè)數(shù)字的所有元素和即為我們想要的數(shù)字。

代碼如下：

intmissingNumber(int*nums,intnumsSize){

intsum1=0;

intsum2=0;

for(inti=0;inumsSize+1;i++)

sum1+=i;

for(inti=0;inumsSize;i++)

sum2+=nums[i];

returnsum1-sum2;

}

法二：異或

思想：

正如示例2，這里假設(shè)一共有10個(gè)數(shù)字，那么這里nums數(shù)組就是[0-9]，不過其中缺了一個(gè)數(shù)字，我們已經(jīng)深知異或的運(yùn)算規(guī)則（相同為0，相異為1）以及兩個(gè)重要結(jié)論：1、兩個(gè)相同的數(shù)字異或等于0。2、0與任何數(shù)字異或等于該任意數(shù)字。因此，我們完全可以先把原數(shù)組的所有元素異或起來，再把理論上0-n依次遞增的所有元素都異或起來，然后兩塊再次異或得到的就是缺少的數(shù)字。

畫圖展示：

代碼如下：

intmissingNumber(int*nums,intnumsSize){

intn=0;

for(inti=0;inumsSize;i++)

n^=nums[i];

for(inti=0;inumsSize+1;i++)

n^=i;

returnn;

}

注意：第二個(gè)for循環(huán)中循環(huán)的次數(shù)要建立在numsSize的基礎(chǔ)上再加1，因?yàn)槭侨鄙倭艘粋€(gè)數(shù)字，所以理論上數(shù)組的長(zhǎng)度是在原基礎(chǔ)上加1的。

題二：（旋轉(zhuǎn)數(shù)組）

鏈接：/problems/rotate-array/

此題的進(jìn)階思想中就明確了使用空間復(fù)雜度為O(1)的算法來解決此問題，正文開始

法一：右旋K次，一次移