【科普】五分鐘快速了解代碼復雜度

大 O 復雜度表示法

如何在不運行代碼的情況下，通過”肉眼“計算出一段代碼的執(zhí)行時間

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

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

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

n = 5

n = 10

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

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

T(n) = O(n)

這就是我們常常說的大 O 表示法

當然了，通過上面的描述，還是有一些抽象的，下面我們再通過一個小栗子來看一下

查找文件

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

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

方法1

依次一個一個的查找

實現(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 資源，當資源少的時候還可以如果是海量資源，那么效率太低了

方法2

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

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

 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ù)量越大的時候，越能體現(xiàn)

對于方法1，通過大 O 表示法可以表示為

T(n) = O(n)

對于方法2，通過大 O 表示法可以表示為

T(n) = O(logn)

很明顯，隨著 n 的增加，logn 會遠遠小于 n，也即是方法2的速度會遠遠快于方法1，這一點我們在上面的實踐當中也有了證明

當然對于常見的復雜度，還有如下這些

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

一般來說，他們的排序順序是這樣的

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

最壞時間復雜度

我們再回到最開始的簡單代碼

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

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

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

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