相信大家對(duì)于算法的時(shí)間復(fù)雜度O都不會(huì)陌生，不過(guò)你知道一個(gè)算法的時(shí)間復(fù)雜度是如何計(jì)算出來(lái)的嗎？
以前在學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)的時(shí)候，對(duì)于每種算法的復(fù)雜度都是死記的并沒(méi)有真正的去研究他們是如何計(jì)算出來(lái)，最近突然對(duì)算法產(chǎn)生了興趣，迫使自己研究了一下算法復(fù)雜度的計(jì)算方法。
概念
大O表示法表示時(shí)間復(fù)雜性，注意它是某一個(gè)算法的時(shí)間復(fù)雜性。大O表示只是說(shuō)有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個(gè)上界，但并不是上確界，但人們?cè)诒硎镜臅r(shí)候一般都習(xí)慣表示前者。
另外除了這個(gè)官方概念，個(gè)人認(rèn)為大O表示的是問(wèn)題規(guī)模n和算法中語(yǔ)句執(zhí)行次數(shù)的關(guān)系。
以二分查找為例，我們求解它的時(shí)間復(fù)雜度
1 設(shè)規(guī)模為n個(gè)元素時(shí)，要執(zhí)行T(n)次
T(n)=T(n/2)+1
T(n)=[T(n/4)+1]+1
…
T(n)=T(n/2^m)+m
當(dāng)n=2^m
T(n)=T(1)+log2n
T(1)=1
所以其算法復(fù)雜度為O（log2n）