學(xué)習(xí)算法的讀書(shū)筆記
據(jù)說(shuō), 學(xué)習(xí)算法時(shí), 時(shí)間復(fù)雜度是精髓, 把時(shí)間復(fù)雜度搞清楚, 算法就學(xué)成一半了?
為什么要學(xué)習(xí)復(fù)雜度分析
算法寫(xiě)完之后, 通過(guò)實(shí)際測(cè)量, 監(jiān)控, 就可以得到比較準(zhǔn)確的時(shí)間, 空間消耗, 那為什么還要學(xué)習(xí)復(fù)雜度呢? 這種辦法是正確的, 但是這叫做事后分析法. 這種辦法有很大局限.
- 受環(huán)境影響
同一數(shù)據(jù)量, 同一代碼, 在不同環(huán)境, 運(yùn)行結(jié)果肯定是不一樣的. 甚至運(yùn)行的結(jié)果截然相反, 反差巨大
- 數(shù)據(jù)的影響
同一環(huán)境, 同一代碼, 隨著數(shù)據(jù)規(guī)模的變化, 并不一定是線性趨勢(shì). 例如排序, 數(shù)據(jù)的規(guī)模, 質(zhì)量都有很大的影響, 如果數(shù)據(jù)恰好有序, 那么進(jìn)行一次冒泡排序用時(shí)就非常短.
綜上所述, 我們需要一個(gè)不用具體去測(cè)試, 就可以粗略的估計(jì)出算法的執(zhí)行效率的辦法. 這就是所謂的時(shí)間, 空間復(fù)雜度分析方法.
大 O 復(fù)雜度分析法
對(duì)于算法的執(zhí)行效率, 簡(jiǎn)單說(shuō)就是代碼的執(zhí)行時(shí)間, 但是怎么在不允許代碼的情況下, 一下看出一段代碼的執(zhí)行時(shí)間呢?
/**
* 計(jì)算 1,2,3...n 的加和
*
* @param n
* @return
*/
public static int plus(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum = sum + i;
}
return sum;
}
在粗略估計(jì)的情況下, 假設(shè)每行代碼的計(jì)算時(shí)間是一樣的, 那么執(zhí)行時(shí)間是多久? 如果假設(shè)每一行代碼的運(yùn)行時(shí)間定義為unit.
代碼int sum=0運(yùn)行時(shí)間為1*unit, sum = sum + i這行代碼的運(yùn)行總時(shí)間為n*unit,return sum;運(yùn)行時(shí)間為1*unit, 那么最終就可以算出這段代碼的總運(yùn)行時(shí)間為 (2+n)*unit. 這時(shí)候就可以得出一個(gè)結(jié)論: 這段代碼的執(zhí)行時(shí)間T(n)與代碼的執(zhí)行次數(shù)成正比
總結(jié)為公式就是 :
T(n)的含義是代碼的執(zhí)行時(shí)間, 其中n為數(shù)據(jù)規(guī)模的大小.f(n)為每行代碼的執(zhí)行的次數(shù)總和. 因?yàn)檫@是一個(gè)公式所以用f(n)表示. 那么O, 就是T(n)與f(n)成正比. 這就是大O時(shí)間復(fù)雜度表示法. 它并不是表示代碼的執(zhí)行時(shí)間, 而是表示代碼隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)! 這就是時(shí)間復(fù)雜度.
如果n很大,例如1000000000, 那么(2+n)中的2, 就可以忽略了, 所以上面公式就可以是: T(n)=O(n). 即它的時(shí)間復(fù)雜度為 n. 總結(jié)起來(lái)就是: 公式中的低階, 系數(shù), 常量值都可以忽略, 因?yàn)樗麄儾粫?huì)左右增長(zhǎng)的趨勢(shì),
時(shí)間復(fù)雜度分析
下面會(huì)有三個(gè)辦法來(lái)幫助你進(jìn)行時(shí)間復(fù)雜度分析:
1. 只關(guān)注循環(huán)次數(shù)最多的代碼
上面的代碼中, 循環(huán)次數(shù)最多的代碼無(wú)疑就是sum = sum + i;, 那么我們只要關(guān)注他就可以了,時(shí)間復(fù)雜度就是O(n), 例如下面的偽代碼:
for(int j = 1; j<=n: j++){
for (int i = 1; i <= n; i++) {
sum = sum + i;
}
}
代碼 sum = sum + i;的循環(huán)次數(shù)是n的平方, 那么時(shí)間復(fù)雜度就是O(n^2)
2. 總的復(fù)雜度就是量級(jí)最大那段代碼的復(fù)雜度
下面的偽代碼:
for(int j = 1; j<=n: j++){
other = other + j;
for (int i = 1; i <= n; i++) {
sum = sum + i;
}
}
代碼other = other + j;運(yùn)行次數(shù)為n, 而sum = sum + i;運(yùn)行次數(shù)為n2,所以最后的復(fù)雜度也是O(n2)
3. 嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
如果循環(huán)里面只有一行代碼,然后這行代碼調(diào)用了另外一個(gè)函數(shù)f(), 這個(gè)f()也是一層循環(huán), 那么最后的復(fù)雜度就是他們的乘積
上面的技巧其實(shí)不用刻意去記, 因?yàn)槎嗫淳吐斫饬?/p>
幾種常見(jiàn)的復(fù)雜度
常見(jiàn)的復(fù)雜度如下:
# 常量階
O(1)
# 對(duì)數(shù)階
O(logn)
# 線性階
O(n)
# 線性對(duì)數(shù)階
O(nlogn)
# 平方階,立方階....M次方階
O(n^2),O(n^3),O(n^m)
# 指數(shù)階
O(2^n)
# 階乘階
O(n!)
如果按多項(xiàng)式和費(fèi)多項(xiàng)式來(lái)分類, 那么只有倒數(shù)兩個(gè)是多項(xiàng)式,其他的為單項(xiàng)式. 數(shù)據(jù)規(guī)模增大的時(shí)候, 非多項(xiàng)式的執(zhí)行時(shí)間會(huì)急劇增加, 所以非多項(xiàng)式復(fù)雜度的算法是非常抵消的. 下面調(diào)一個(gè)例子來(lái)說(shuō)明上面的復(fù)雜度.
- O(nlogn) 或 O(logn)
看下面的代碼片段:
int i = 1;
while (i <= n) {
i = i * 2;
}
根據(jù)之前講的原則, 我們只計(jì)算 i = i * 2;的執(zhí)行次數(shù), i的初始值是1, 每循環(huán)一次, 它就乘以2, 直到 小于或等于n時(shí), 停止計(jì)算, 那么將i的值變化過(guò)程總結(jié)一下就是:
也就是說(shuō)當(dāng)時(shí)候等于n, 那么直到k是多少, 就知道了這行代碼的運(yùn)行次數(shù).計(jì)算k值就很簡(jiǎn)單了, 高中數(shù)學(xué)水平就可以算出
, 不管是以多少為底, 只要是一個(gè)常量, 我們就可以將它忽略, 將這一復(fù)雜度統(tǒng)一定為: O(logn). 所以即使將
i = i * 2;變?yōu)?code>i = i * 3;, 它的時(shí)間復(fù)雜度也是O(logn).
最好, 最壞時(shí)間復(fù)雜度
看下面的代碼:
public static int find(int[] array, int m) {
int n = array.length;
for (int i = 0; i < n; i++) {
if (array[i] == m){
return i;
}
}
return -1;
}
代碼的含義為: 查找數(shù)組中, 值為m的角標(biāo), 如果找到了, 停止程序并返回其下標(biāo). 很容易可以看出. 如果第一次循環(huán)就找到了, 此時(shí)的復(fù)雜度就是O(1), 如果沒(méi)有此值或此值在數(shù)組最后位置上, 此時(shí)的復(fù)雜度就是O(n), 有最好, 最壞復(fù)雜度, 那么平均復(fù)雜度該是多少?
平均時(shí)間復(fù)雜度
還是上面的例子, 查找m在數(shù)組中的位置, 可以分為兩類可能:
在數(shù)組的0 ~ n-1 位置上
不在數(shù)組中
第一種情況下, 所有的次數(shù)加起來(lái)應(yīng)該等于 1+2+3+4+ ... +n, 第二中情況, 次數(shù)是個(gè)定值 n. 所以這兩大種情況加起來(lái), 總共的執(zhí)行次數(shù)是: 1+2+3+4+ ... +n+n
兩種情況中, m出線在數(shù)組中的位置, 自然就是有n+1中可能. 總的次數(shù), 除以n+1, 就是它的平均復(fù)雜度. 總結(jié)成公式就是:
去掉低階, 常量之后, 上面的公式最終就簡(jiǎn)化為 O(n)
