目錄

一.什么是算法的時(shí)間復(fù)雜度

二.如何分析一個(gè)算法的時(shí)間復(fù)雜度

1.有確定次數(shù)的算法

2.次數(shù)不確定的算法

---

一.什么是算法的時(shí)間復(fù)雜度

????????時(shí)間復(fù)雜度是一個(gè)函數(shù) ，定性描述一個(gè)算法（程序）的運(yùn)行時(shí)間。它可以是漸近的，亦即考察輸入值大小趨近無窮時(shí)的情況。正常情況下，完成相同的任務(wù)的時(shí)間復(fù)雜度越低，算法越優(yōu)。

? ? ? ? 比如 求從1到100的和的兩種方法 的時(shí)間復(fù)雜度：

int i，sum = 0, n = 100; for (i = 1; i <=n; i++){sum += i; } printf ("%d", sum);

-時(shí)間復(fù)雜度為O(n)-

int sum = 0, n = 100; sum = (1 + n) * n/2; printf ("%d", sum);

-時(shí)間復(fù)雜度為O(1)-

????????大O記法：用大寫O（）來體現(xiàn)算法時(shí)間復(fù)雜度的記法叫大O記法。

二.如何分析一個(gè)算法的時(shí)間復(fù)雜度

? ? ? ? 大O階推推導(dǎo)法三個(gè)步驟：

????????(1).用常數(shù)1取代運(yùn)行時(shí)間中所有加法常數(shù)。

? ? ? ? (2).在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。

? ? ? ? (3).如果最高階項(xiàng)存在且其系數(shù)不是1，則去除與這個(gè)項(xiàng)相乘的系數(shù)。

? ? ? ? -得到的結(jié)果就是大O階。(只看文字有些難以理解，可以先看看后面的實(shí)例)

針對時(shí)間復(fù)雜度，我將算法分為有確定次數(shù)和次數(shù)不確定的算法。

下面從兩個(gè)方面分析幾個(gè)實(shí)例：（ f(n)表示程序運(yùn)行的次數(shù)?）

1.有確定次數(shù)的算法

-常數(shù)階-

int sum = 0, n = 100; sum = (1 + n) * n/2; printf ("%d", sum);

? ? ? ? 這個(gè)算法的f(n)為3，根據(jù)法(1)其時(shí)間復(fù)雜度為O(1)。

常數(shù)項(xiàng)對函數(shù)的增長速度影響并不大，所以當(dāng) f(n) = c，c 為一個(gè)常數(shù)的時(shí)候，我們說這個(gè)算法的時(shí)間復(fù)雜度為 O(1)；如果 T(n) 不等于一個(gè)常數(shù)項(xiàng)時(shí)，直接將常數(shù)項(xiàng)省略。

-線性階-

int i; for (i = 0; i < n; i++){/*時(shí)間復(fù)雜度為O(1)的程序*/ }

這個(gè)算法的f(n)為n，故其時(shí)間復(fù)雜度為O(n)。

-對數(shù)階-

int count = 1; while (count < n) {count = count * 2;/*時(shí)間復(fù)雜度為O(1)的程序*/ }

由于2^x=n得到x=（log2）n。所以f(n)為(log2)n，其時(shí)間復(fù)雜度為O(logn)。

-平方階-

int i,j; for (i = 0; i < n; i++) {for (j = 0; j < n; j++){/*時(shí)間復(fù)雜度為O(1)的程序*/ } }

這是個(gè)嵌套循環(huán)，可以成將時(shí)間復(fù)雜度為O(n)的語句執(zhí)行了n次。故其時(shí)間復(fù)雜度為（n^2）。

若外循環(huán)次數(shù)改為m，則時(shí)間復(fù)雜度變?yōu)?#xff08;m*n）。

int i,j; for (i = 0; i < n; i++) {for (j = i; j < n; j++) /*此處0換成i*/ {/*時(shí)間復(fù)雜度為O(1)的程序*/ } }

而對于這個(gè)算法，其f(n)=n+(n-1)+(n-2)...+1=n(n+1)/2=(n^2)/2+n/2。

我們知道高次項(xiàng)對于函數(shù)的增長速度的影響是最大的。n^2?的增長速度是遠(yuǎn)超 n的，因?yàn)橐蟮木炔桓?#xff0c;所以直接忽略較低項(xiàng)n/2。

又因?yàn)楹瘮?shù)的階數(shù)對函數(shù)的增長速度的影響是最顯著的，所以忽略與最高階相乘的常數(shù)1/2。

方法(1)：沒有加法常數(shù)不予考慮；(2)：只保留最高項(xiàng)，故保留(n^2)/2；(3)：去除項(xiàng)的系數(shù)1/2。

故其時(shí)間復(fù)雜度為O(n^2)。

-再舉例,若一個(gè)算法的f(n)=(n^3)*3/2+(n^2)*3/2+n+5時(shí),根據(jù)推導(dǎo)大O階法其時(shí)間復(fù)雜度為O(n^3)。

-其他情況-

int i, j, sum = 0, n = 100; for (i = 1; i <=n; i++){sum += i; } printf ("%d\n", sum); for (i = 1; i <=n; i++){for(j = 1; j <=n; j++){sum+=i*j;} }

對于順序執(zhí)行的語句或者算法，總的時(shí)間復(fù)雜度等于其中最大的時(shí)間復(fù)雜度。

此時(shí)時(shí)間復(fù)雜度為 max(O(n^2), O(n))，即 O(n^2)。

常見的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從大到小依次是：

????????O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

2.次數(shù)不確定的算法

? ? ? ? 最壞情況與平均情況：若要查找一個(gè)有n個(gè)隨機(jī)數(shù)字?jǐn)?shù)組中的某個(gè)數(shù)字，最好的情況第一個(gè)數(shù)字就是，那么算法的時(shí)間復(fù)雜度為O(1)，最壞的情況是最后一個(gè)，則時(shí)間復(fù)雜度為O(n)。而平均運(yùn)行時(shí)間為查找n/2次后發(fā)現(xiàn)目標(biāo)元素。平均運(yùn)行時(shí)間是所有情況中最有意義的，因?yàn)樗瞧谕倪\(yùn)行時(shí)間。但現(xiàn)實(shí)是平均運(yùn)行時(shí)間很難通過分析得到，所以在沒有特殊說明的情況下，提到的時(shí)間復(fù)雜度都指最壞時(shí)間復(fù)雜度。

-冒泡排序-

int a[n] = {}; for (int i = 0; i < n - 1; i++) {for (int j; j < n-i-1; j++){if (a[j] > a[j+1]) swap(a[j],a[j+1]); /*swap已定義好*/} }

最壞的情況即待排序列為逆序時(shí)，f(n)=1+2+3...+(n-1)=n*(n-1)/2次，故其時(shí)間復(fù)雜度為O(n^2)。

總結(jié)

以上是生活随笔為你收集整理的简单分析算法的时间复杂度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。