寫在前面:
這篇文章是在公衆号: 程式員小灰 中釋出的。是我到目前為止所看到的關于時間複雜度介紹的最好的文章,簡介 清晰 明了。
是以拿來po出來 僅供學習交流,如侵則删。
現已将此文收錄至: 《資料結構》C語言版 (清華嚴蔚敏考研版) 全書知識梳理
正文:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZlBna9QXbm9Fe39DM0YzLcFFR1J3MyBXMFl1MZRUU0NDOwJTd6F2S2VjW0hFaVhTeZp3aJd3ZrZ3NwNDNhdzRil2TyN2cuVnV1wkTGdVSV1kMTVVZRhlWvJHb2QEcHplSsFWazVzT050LcdGcq9lepJWbt9CXuNmLjlGcx5iepJWbt9CXvwlOzBHd0h2Pw9CX0Vmbu4GZzNmLzN3Lc9CX6MHc0RHaiojIsJye.jpg)
時間複雜度的意義
究竟什麼是時間複雜度呢?讓我們來想象一個場景:某一天,小灰和大黃同時加入了一個公司......
一天過後,小灰和大黃各自傳遞了代碼,兩端代碼實作的功能都差不多。大黃的代碼運作一次要花100毫秒,記憶體占用5MB。小灰的代碼運作一次要花100秒,記憶體占用500MB。于是......
由此可見,衡量代碼的好壞,包括兩個非常重要的名額:
1.運作時間;
2.占用空間。
基本操作執行次數
關于代碼的基本操作執行次數,我們用四個生活中的場景,來做一下比喻:
場景1:給小灰一條長10寸的面包,小灰每3天吃掉1寸,那麼吃掉整個面包需要幾天?
答案自然是 3 X 10 = 30天。
如果面包的長度是 N 寸呢?
此時吃掉整個面包,需要 3 X n = 3n 天。
如果用一個函數來表達這個相對時間,可以記作 T(n) = 3n。
場景2:給小灰一條長16寸的面包,小灰每5天吃掉面包剩餘長度的一半,第一次吃掉8寸,第二次吃掉4寸,第三次吃掉2寸......那麼小灰把面包吃得隻剩下1寸,需要多少天呢?
這個問題翻譯一下,就是數字16不斷地除以2,除幾次以後的結果等于1?這裡要涉及到數學當中的對數,以2位底,16的對數,可以簡寫為log16。
是以,把面包吃得隻剩下1寸,需要 5 X log16 = 5 X 4 = 20 天。
如果面包的長度是 N 寸呢?
需要 5 X logn = 5logn天,記作 T(n) = 5logn。
場景3:給小灰一條長10寸的面包和一個雞腿,小灰每2天吃掉一個雞腿。那麼小灰吃掉整個雞腿需要多少天呢?
答案自然是2天。因為隻說是吃掉雞腿,和10寸的面包沒有關系 。
如果面包的長度是 N 寸呢?
無論面包有多長,吃掉雞腿的時間仍然是2天,記作 T(n) = 2。
場景4:給小灰一條長10寸的面包,小灰吃掉第一個一寸需要1天時間,吃掉第二個一寸需要2天時間,吃掉第三個一寸需要3天時間.....每多吃一寸,所花的時間也多一天。那麼小灰吃掉整個面包需要多少天呢?
答案是從1累加到10的總和,也就是55天。
如果面包的長度是 N 寸呢?
此時吃掉整個面包,需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。
記作 T(n) = 0.5n^2 + 0.5n。
上面所講的是吃東西所花費的相對時間,這一思想同樣适用于對程式基本操作執行次數的統計。剛才的四個場景,分别對應了程式中最常見的四種執行方式:
場景1:T(n) = 3n,執行次數是線性的。
- void eat1(int n){
- for( int i= ; i<n; i++){;
- System. out.println( "等待一天");
- System. out.println( "等待一天");
- System. out.println( "吃一寸面包");
- }
- }
- vo
場景2:T(n) = 5logn,執行次數是對數的。
- void eat2(int n){
- for( int i= ; i<n; i*= ){
- System. out.println( "等待一天");
- System. out.println( "等待一天");
- System. out.println( "等待一天");
- System. out.println( "等待一天");
- System. out.println( "吃一半面包");
- }
- }
場景3:T(n) = 2,執行次數是常量的。
- void eat3(int n){
- System. out.println( "等待一天");
- System. out.println( "吃一個雞腿");
- }
場景4:T(n) = 0.5n^2 + 0.5n,執行次數是一個多項式。
- void eat4(int n){
- for( int i= ; i<n; i++){
- for( int j= ; j<i; j++){
- System. out.println( "等待一天");
- }
- System. out.println( "吃一寸面包");
- }
- }
漸進時間複雜度
有了基本操作執行次數的函數 T(n),是否就可以分析和比較一段代碼的運作時間了呢?還是有一定的困難。
比如算法A的相對時間是T(n)= 100n,算法B的相對時間是T(n)= 5n^2,這兩個到底誰的運作時間更長一些?這就要看n的取值了。
是以,這時候有了漸進時間複雜度(asymptotic time complectiy)的概念,官方的定義如下:
若存在函數 f(n),使得當n趨近于無窮大時,T(n)/ f(n)的極限值為不等于零的常數,則稱 f(n)是T(n)的同數量級函數。
記作 T(n)= O(f(n)),稱O(f(n)) 為算法的漸進時間複雜度,簡稱時間複雜度。
漸進時間複雜度用大寫O來表示,是以也被稱為大O表示法。
如何推導出時間複雜度呢?有如下幾個原則:
- 如果運作時間是常數量級,用常數1表示;
- 隻保留時間函數中的最高階項;
- 如果最高階項存在,則省去最高階項前面的系數。
讓我們回頭看看剛才的四個場景。
場景1:
T(n) = 3n
最高階項為3n,省去系數3,轉化的時間複雜度為:
T(n) = O(n)
場景2:
T(n) = 5logn
最高階項為5logn,省去系數5,轉化的時間複雜度為:
T(n) = O(logn)
場景3:
T(n) = 2
隻有常數量級,轉化的時間複雜度為:
T(n) = O(1)
場景4:
T(n) = 0.5n^2 + 0.5n
最高階項為0.5n^2,省去系數0.5,轉化的時間複雜度為:
T(n) = O(n^2)
這四種時間複雜度究竟誰用時更長,誰節省時間呢?稍微思考一下就可以得出結論:
O(1)< O(logn)< O(n)< O(n^2)
在程式設計的世界中有着各種各樣的算法,除了上述的四個場景,還有許多不同形式的時間複雜度,比如:
O(nlogn), O(n^3), O(m*n),O(2^n),O(n!)
今後遨遊在代碼的海洋裡,我們會陸續遇到上述時間複雜度的算法。
時間複雜度的巨大差異
我們來舉過一個栗子:
算法A的相對時間規模是T(n)= 100n,時間複雜度是O(n)
算法B的相對時間規模是T(n)= 5n^2,時間複雜度是O(n^2)
算法A運作在小灰家裡的老舊電腦上,算法B運作在某台超級計算機上,運作速度是老舊電腦的100倍。
那麼,随着輸入規模 n 的增長,兩種算法誰運作更快呢?
從表格中可以看出,當n的值很小的時候,算法A的運作用時要遠大于算法B;當n的值達到1000左右,算法A和算法B的運作時間已經接近;當n的值越來越大,達到十萬、百萬時,算法A的優勢開始顯現,算法B則越來越慢,差距越來越明顯。
這就是不同時間複雜度帶來的差距。
還有一個連結,這個裡面有很多關于時間複雜度的例子,一定要看https://www.jianshu.com/p/f4cca5ce055a