常碰到的時(shí)間復(fù)雜度
其中指數(shù)階和階乘階都屬于十分低效的復(fù)雜度量級(jí)，應(yīng)該盡量避免漓踢。
時(shí)間復(fù)雜度.png
下面這段代碼的時(shí)間復(fù)雜度為log(n)
//這段代碼的時(shí)間負(fù)責(zé)度就是log(n)
i=1;
while (i <= n) {
i = i * 2;
}
最好與最壞情況下的時(shí)間復(fù)雜度
- 最好時(shí)間復(fù)雜度
- 最壞時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度
最好時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都很好理解青责，那么什么是平均復(fù)雜度呢扁耐？
我們先看下面代碼：
// n 表示數(shù)組 array 的長(zhǎng)度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
- 最好時(shí)間復(fù)雜度為O(1)做葵，最壞時(shí)間復(fù)雜度為O(N)；
-
平均時(shí)間復(fù)雜度計(jì)算如下：
要查找的變量 x 在數(shù)組中的位置瘫筐，有 n+1 種情況（n種找到策肝、1種未找到）拙毫，這n+1種情況分別查找1缀蹄、2、3....n-1衅码、n逝段、n次夭谤，那么平均時(shí)間復(fù)雜度如下：
計(jì)算過程.png
如果假設(shè)找到與沒找到的概率都為1/2颊乘，那么加權(quán)平均時(shí)間復(fù)雜度（期望時(shí)間復(fù)雜度）為：
加權(quán)平均時(shí)間復(fù)雜度計(jì)算.png
平均時(shí)間復(fù)雜度和加權(quán)平均時(shí)間復(fù)雜度都為O(n)，我們?cè)诳紤]時(shí)間復(fù)雜度時(shí)只考慮量級(jí)的變化檩小，并不考慮k值规求。
