怎樣做自己的公司網(wǎng)站百度在線(xiàn)
目錄
1 時(shí)間復(fù)雜度
2 大O漸進(jìn)表示法
舉例子（計(jì)算時(shí)間復(fù)雜度為多少）
3 空間復(fù)雜度
前言：復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度，兩者是不同維度的，所以比較不會(huì)放在一起比較，但是時(shí)間復(fù)雜度和空間復(fù)雜度是用來(lái)衡量一個(gè)算法是否好壞的標(biāo)準(zhǔn)，時(shí)間復(fù)雜度用來(lái)描述算法運(yùn)行的時(shí)間快慢，空間復(fù)雜度用來(lái)衡量一個(gè)算法所需要的額外空間。最初的計(jì)算機(jī)時(shí)代計(jì)算機(jī)的存儲(chǔ)量很小，所以額外注重空間復(fù)雜度，隨著發(fā)展，計(jì)算機(jī)的存儲(chǔ)已經(jīng)不是讓人擔(dān)心的點(diǎn)了，所以更為注重時(shí)間復(fù)雜度。
1 時(shí)間復(fù)雜度
時(shí)間復(fù)雜度的定義上可以認(rèn)為使勁按復(fù)雜度是一個(gè)函數(shù)，定量的描述了算法所需要的時(shí)間，但是理論上來(lái)說(shuō)，運(yùn)行的時(shí)間是要上機(jī)測(cè)試才能測(cè)試出來(lái)的，實(shí)際測(cè)試就會(huì)花很多時(shí)間，所以有了時(shí)間復(fù)雜度這個(gè)分析方式分析算法中執(zhí)行的基本操作的次數(shù)，認(rèn)定為時(shí)間復(fù)雜度。
int main()
{for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){//測(cè)試語(yǔ)句}}for (int i = 0; i < N; i++){//測(cè)試語(yǔ)句}int M = 10;while (M--){//測(cè)試語(yǔ)句}return 0;
}這段代碼的時(shí)間復(fù)雜度是？
兩個(gè)嵌套的for循環(huán)，也就是執(zhí)行了N^2次，再來(lái)一個(gè)for循環(huán)，執(zhí)行次數(shù)為N，最后while收尾，執(zhí)行次數(shù)為10,所以時(shí)間復(fù)雜度的函數(shù)為F(N) = N^2 + N + 10，隨著N的增大，式子的值會(huì)大到無(wú)法想象?，這都得益于N^2，那么整個(gè)式子的決定性因素是N^2，所以我們就認(rèn)為時(shí)間復(fù)雜度是N^2。
這種估算的方法被稱(chēng)為大O漸進(jìn)表示法，只取式子中的決定性因素。
2 大O漸進(jìn)表示法
計(jì)算時(shí)間復(fù)雜度的時(shí)候我們通常采用大O漸進(jìn)表示法，推導(dǎo)大O階的表示方法為：
1、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2、在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
3、如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。
這里其實(shí)完全可以類(lèi)比高中的數(shù)學(xué)函數(shù)，y = x，x可以是2x也可以是3x，這就是為什么舍棄常數(shù)的原因，x和2x是沒(méi)有區(qū)別的。
那么什么是加法常數(shù)呢？只要沒(méi)有循環(huán)或者遞歸，我們都可以認(rèn)為執(zhí)行次數(shù)為O(1)，哪怕是寫(xiě)了一萬(wàn)行代碼。
執(zhí)行程序的時(shí)候會(huì)存在最好情況 最壞情況 以及平均情況（期望值），一般計(jì)算時(shí)間復(fù)雜度的時(shí)候都是計(jì)算的最壞情況，所以像冒泡排序，運(yùn)氣好點(diǎn)，時(shí)間復(fù)雜度就是O(1),運(yùn)氣不好就是O(N^2)了。
舉例子（計(jì)算時(shí)間復(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 ", count);
}第一個(gè)for循環(huán)的執(zhí)行次數(shù)為2 * N次，第二個(gè)while循環(huán)執(zhí)行次數(shù)為10次，那么函數(shù)表達(dá)式就是2*N + 10,根據(jù)大O表示法，時(shí)間復(fù)雜度為O(N)。
void Fun3(int N, int M)
{int count = 0;for (int k = 0; k < M; k++){count++;}for (int k = 0; k < N; k++){count++;}printf("%d ", count);
}第一個(gè)for循環(huán)執(zhí)行次數(shù)為M次，第二個(gè)for循環(huán)的執(zhí)行次數(shù)為N次，那么函數(shù)表達(dá)式就是O(M + N)，
那么最后結(jié)果視結(jié)果而定，如果M遠(yuǎn)大于N，那么時(shí)間復(fù)雜度就是O(M)，那么N >> M同理可得。
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; k++){count++;}printf("%d", count);
}根據(jù)第一個(gè)for循環(huán)的循環(huán)條件，循環(huán)次數(shù)為100次，是常數(shù)，所以時(shí)間復(fù)雜度就是O(1)。
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; end--){int flag = 0;for (size_t i = 1; i < end; i++){if (a[i - 1] > a[i]){swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0){break;}}
}冒泡排序嚴(yán)格意義上來(lái)說(shuō)不是標(biāo)準(zhǔn)的O(N^2)，因?yàn)樗膱?zhí)行次數(shù)在隨著程序的執(zhí)行是逐漸減少的，最開(kāi)始兩兩比較的次數(shù)是N- 1，每趟下來(lái)，就會(huì)確定一個(gè)數(shù)據(jù)的位置，所以?xún)蓛杀容^的次數(shù)每次都會(huì)減去1，那么if這個(gè)語(yǔ)句執(zhí)行的次數(shù)就是N - 1 N - 2……1,利用高中的等差數(shù)列的知識(shí)，可以得到時(shí)間復(fù)雜度的函數(shù)是F(N) = (N - 1) * (N - 1 + 1) / 2，根據(jù)大O表示法，可得得出復(fù)雜度為O(N^2)。
int BinarySeatch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;//[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;elsereturn mid;}return -1;
}
這是一個(gè)典型的二分查，時(shí)間復(fù)雜度為直接看是看不出來(lái)的，所以有的代碼計(jì)算時(shí)間復(fù)雜度是要結(jié)合畫(huà)圖的：
我們討論最壞情況，二分查找的本質(zhì)就是不斷的縮小區(qū)間，一半一半的縮短，那么最開(kāi)始有N個(gè)值，就有N/2/2/2/2/2/2……=? 1，那么執(zhí)行次數(shù)就是找的次數(shù)就是除以2的次數(shù)，計(jì)算方式就是
N = 2^x，x是執(zhí)行的次數(shù)，我們求的就是x的值，那么利用高中的換底公式，我們可以得到
x是以2為底，N的對(duì)數(shù)，而因?yàn)閷?duì)數(shù)不太好寫(xiě)，除非使用專(zhuān)業(yè)的公式編輯器，所以默認(rèn)規(guī)定LogN,表示的就是以2為底，N的對(duì)數(shù)，如果有其他底數(shù)，就照常寫(xiě)。
long long Fac(size_t N)
{if (0 == N){return 1;}return Fac(N - 1) * N;
}
計(jì)算階乘遞歸的時(shí)間復(fù)雜度，遞歸，會(huì)多次開(kāi)辟函數(shù)棧幀，所以一次遞歸，就會(huì)開(kāi)辟一個(gè)函數(shù)棧幀，執(zhí)行次數(shù)是1，那么遞歸n次，總執(zhí)行次數(shù)就是N，所以時(shí)間復(fù)雜度就是O(N)。
引申：
long long Fac(size_t N)
{if (0 == N)return 1;for (int i = 0; i < N; i++){//測(cè)試語(yǔ)句}return Fac(N - 1) * N;
}
?遞歸函數(shù)里面加了一個(gè)for循環(huán)，時(shí)間復(fù)雜度是多少呢？
不加for循環(huán)之前，每個(gè)函數(shù)的時(shí)間復(fù)雜度是O(1)，開(kāi)辟了N個(gè)函數(shù)，那么復(fù)雜度就是O(N)，但是現(xiàn)在每個(gè)函數(shù)的時(shí)間復(fù)雜度就是O(N)了，因?yàn)槊總€(gè)子函數(shù)里面都有一個(gè)for循環(huán)，所以N個(gè)O(N)的函數(shù)放在一起，時(shí)間復(fù)雜度就是O(N ^ 2)。
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
我們知道遞歸用來(lái)計(jì)算斐波那契數(shù)列是非常不劃算的，因?yàn)橹貜?fù)計(jì)算的次數(shù)太多了，是次方級(jí)別的重復(fù)：
像這樣，函數(shù)執(zhí)行的次數(shù)是從2的0次方開(kāi)始，一直到2的N次方，那么利用高中的等比數(shù)列的公式，可以得出時(shí)間復(fù)雜度為函數(shù)為F(N) = 2^N - 1,所以時(shí)間復(fù)雜度就是O(2 ^ N)。
這是非?？植赖?#xff0c;所以計(jì)算斐波那契數(shù)列的話(huà)還是使用迭代吧！
3 空間復(fù)雜度
時(shí)間復(fù)雜度可以理解為語(yǔ)句的執(zhí)行次數(shù)，空間復(fù)雜度可以理解額外開(kāi)辟的空間，也是采用的大O漸進(jìn)表示法。當(dāng)然，空間復(fù)雜度不是多少字節(jié)，意義不大，因?yàn)楫?dāng)前的計(jì)算機(jī)存儲(chǔ)足夠大，所以空間復(fù)雜度表示的是變量的個(gè)數(shù)，需要注意的是：函數(shù)需要的?？臻g在編譯期間就已經(jīng)確定好了，所以計(jì)算空間復(fù)雜度靠的是程序運(yùn)行時(shí)候顯示出來(lái)的額外空間。
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; end--){int flag = 0;for (size_t i = 1; i < end; i++){if (a[i - 1] > a[i]){swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0){break;}}
}計(jì)算冒泡排序的空間復(fù)雜度：
?這個(gè)函數(shù)里面有變量，但是是有限個(gè)的，如end flag i ，并沒(méi)有額外開(kāi)辟空間，所以空間復(fù)雜度是O(1)，畢竟是沒(méi)有額外申請(qǐng)空間的。
那么遞歸計(jì)算斐波那契數(shù)列的空間復(fù)雜度是多少呢？
在此之前我們先看這串代碼：
void Test1()
{int a = 10;printf("%p\n", &a);
}
void Test2()
{int b = 10;printf("%p\n", &b);
}
int main()
{Test1();Test2();return 0;
}試問(wèn)運(yùn)行結(jié)果是不是一樣的？有人就會(huì)問(wèn)了，不同函數(shù)存的地址肯定不是一樣的啊，一般情況是這樣的，但是如果兩個(gè)函數(shù)連續(xù)調(diào)用，并且函數(shù)的功能一樣，對(duì)空間的需求是一樣的，那么內(nèi)存在棧上的空間分配就不會(huì)額外開(kāi)辟空間，也就是說(shuō)一個(gè)函數(shù)調(diào)用完后，另一個(gè)函數(shù)就會(huì)接著使用這塊空間，所以地址是一樣的。
那么類(lèi)比到斐波那契數(shù)列的重復(fù)計(jì)算里面：
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
實(shí)際上上開(kāi)辟的空間都是為了計(jì)算函數(shù)Fib(N)到Fib(1)的，函數(shù)的功能是一樣，對(duì)空間的需求也是一樣的，所以重復(fù)計(jì)算的時(shí)候就不會(huì)單獨(dú)開(kāi)辟空間，所以需要計(jì)算的，都用了開(kāi)辟的Fib(N)到Fib(1)的空間，那么空間復(fù)雜度就是O(N)。
感謝閱讀！