大 O 復(fù)雜度表示法

如何在不運(yùn)行代碼的情況下，通過(guò)”肉眼“計(jì)算出一段代碼的執(zhí)行時(shí)間

一段簡(jiǎn)單的 Python 代碼，求1,2,3…n的累加和

1def?cal(n):
2??sum?=?0
3??for?i?in?range(n):
4????sum?+=?i
5??return?sum

對(duì)于上面的一段簡(jiǎn)單代碼，我們輸入不同的 n 值，來(lái)看一下代碼執(zhí)行的效果

n = 5

n = 10

其實(shí)上面的代碼實(shí)在是簡(jiǎn)單，不用說(shuō)也知道 n 不同時(shí)，代碼的執(zhí)行過(guò)程是怎樣的

而我們這里要關(guān)注的重點(diǎn)是代碼的3、4行，當(dāng) n = 5 時(shí)，3、4行代碼執(zhí)行了5遍，當(dāng) n = 10 時(shí)，又執(zhí)行了10遍，其實(shí)我們依次類推可以知道，3、4行代碼永遠(yuǎn)都是執(zhí)行 n 遍，那么此時(shí)對(duì)于上面代碼的時(shí)間復(fù)雜度 T(n)，我們就可以表示為

T(n) = O(n)

這就是我們常常說(shuō)的大 O 表示法

當(dāng)然了，通過(guò)上面的描述，還是有一些抽象的，下面我們?cè)偻ㄟ^(guò)一個(gè)小栗子來(lái)看一下

查找文件

比如我這里整理的編程類資源

經(jīng)過(guò)多年的努力，終于學(xué)（收）會(huì)（集）了圖中的所有知識(shí)，那么如果某一天，我想寫一段代碼來(lái)查找 Dubbo 教程，應(yīng)該如何實(shí)現(xiàn)呢

方法1

依次一個(gè)一個(gè)的查找

實(shí)現(xiàn)代碼為

1def?find_source(source_list,?name):
2????for?i?in?source_list:
3????????if?i?==?name:
4????????????return?i

這樣我們需要一直循環(huán)到文件夾26才可以找到 Dubbo 資源，當(dāng)資源少的時(shí)候還可以如果是海量資源，那么效率太低了

方法2

從中間開(kāi)始找，如果發(fā)現(xiàn)小了，就把左邊的都去掉，再在剩下的文件中往中間開(kāi)始找，以此類推

這樣的二分查找，我們只需要在第五次查找的時(shí)候就拿到想要的資源

 1def?find_source(source_list,?name):
 2????min?=?0
 3????ma?=?len(source_list)-1
 4????while?min?<=?max:
 5????????mid?=?(min+max)/2
 6????????if?source_list[mid]?==?name:
 7????????????return?"get?source?at?%s"?%?mid
 8????????if?source_list[mid]? 9????????????min?=?mid?+?1
10????????else:
11????????????max?=?mid?-?1
12????return?"no?source?here!"

可以清晰的看出，第二種方法快了很多，而且在資源數(shù)量越大的時(shí)候，越能體現(xiàn)

對(duì)于方法1，通過(guò)大 O 表示法可以表示為

T(n) = O(n)

對(duì)于方法2，通過(guò)大 O 表示法可以表示為

T(n) = O(logn)

很明顯，隨著 n 的增加，logn 會(huì)遠(yuǎn)遠(yuǎn)小于 n，也即是方法2的速度會(huì)遠(yuǎn)遠(yuǎn)快于方法1，這一點(diǎn)我們?cè)谏厦娴膶?shí)踐當(dāng)中也有了證明

當(dāng)然對(duì)于常見(jiàn)的復(fù)雜度，還有如下這些

O(1), O(n), O(logn), O(nlogn), O(n^2)

一般來(lái)說(shuō)，他們的排序順序是這樣的

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)

最壞時(shí)間復(fù)雜度

我們?cè)倩氐阶铋_(kāi)始的簡(jiǎn)單代碼

1def?cal(n):
2??sum?=?0
3??for?i?in?range(n):
4????sum?+=?i
5??return?sum

可以簡(jiǎn)單的把上述代碼分為兩塊，代碼行2和代碼行3、4
對(duì)于行2，復(fù)雜度為 O(1)，對(duì)于行3、4，復(fù)雜度為 O(n)，一般情況下，我們分析一段代碼的復(fù)雜度時(shí)，基本采用的是復(fù)雜度比較高的那一部分，也即是上述代碼的復(fù)雜度為 O(n)

這里其實(shí)還涉及到了兩個(gè)概念，就是最好情況時(shí)間復(fù)雜度和最壞情況時(shí)間復(fù)雜度，同樣可以看出，O(1) 就是最好情況時(shí)間復(fù)雜度，而 O(n) 就是最壞的情況

好了，以上就是今天我們要分享的內(nèi)容，喜歡就給個(gè)”在看“吧