時間空間複雜度學習總結
點選藍色“ 喬志勇筆記 ”關注我喲
加個“ 星標 ”,第一時間獲取推送的文章哦!
一、程式碼的執行效率 :
快 : 時間複雜度
省: 空間複雜度
二、大O複雜度表示法
T(n)=O(f(n))
n: 資料規模的大小 // 需要重點理解 n 的含義
T(n): 所有程式碼的執行時間
f(n):每行程式碼執行的次數總和
O : 程式碼的執行時間T(n)與f(n)表示式成正比
三、時間複雜度分析
(1)定義:
漸進時間複雜度,演算法的執行時間與資料規模之間的增長關係
(2) 分析方法
1、只關注迴圈執行次數最多的一段程式碼
2、加法法則:總複雜度等於量級最大的那段程式碼的複雜度
3、乘法法則:巢狀程式碼的複雜度等於巢狀內外程式碼複雜度的乘積
(3)常見時間複雜度
1、多項式複雜度:
常量階 O(1) 對數階 O(logn)
線性階 O(n) 線性對數階O(nlogn)
平方階O(n2) 立方階 O(n3) k次方階 O(nk)
2、非多項式複雜度:
指數階 O(2n) 階乘階O(n!)
3、兩個資料的規模來決定的複雜度:
O(m+n) O(m*n)
四、空間複雜度
(1)定義
漸進空間複雜度,演算法的儲存空間與資料規模之間的增長關係
(2)常見空間複雜度
O(1)
O(n)
O(n2)
五、最好、最壞情況時間複雜度
demo:
最好情況時間複雜度 O(1)
最壞情況時間複雜度 O(n)
六、平均情況時間複雜度
(1)定義
全稱是加權平均時間複雜度 或者期望時間複雜度
(2)未考慮概率:
要查詢的變數x在陣列中的位置,有n+1種情況:在陣列的 0 ~ n-1 位置中和不在陣列中。
我們把每種情況下,查詢需要遍歷的元素個數累加起來,然後再除以n+1,就可以得到需要遍歷的元素個數的平均值
(3)應該考慮概率:
加權平均時間複雜度 O(n)
七、均攤時間複雜度
(1)定義
對一個數據結構進行一組連續操作中,大部分情況下時間複雜度都很低,只有個別情況下時間複雜度比較高,而且這些操作之間存在前後連貫的時序關係,這個時候,我們就可以將這一組操作放在一塊兒分析,看是否能將較高時間複雜度那次操作的耗時,平攤到其他那些時間複雜度比較低的操作上。而且,在能夠應用均攤時間複雜度分析的場合,一般均攤時間複雜度就等於最好情況時間複雜度。
均攤時間複雜度就是一種特殊的平均時間複雜度
(2)示例
解析:
當i < len時, 即 i = 0,1,2,...,n-1的時候,for迴圈不走,所以這n次的時間複雜度都是O(1);
當i >= len時, 即 i = n的時候,for迴圈進行陣列的copy,所以只有這1次的時間複雜度是O(n); 由此可知:
該演算法的最好情況時間複雜度(best case time complexity)為O(1); 最壞情況時間複雜度(worst case time complexity)為O(n); 平均情況時間複雜度(average case time complexity), 第一種計算方式: (1+1+...+1+n)/(n+1) = 2n/(n+1) 【注: 式子中1+1+...+1中有n個1】,所以平均複雜度為O(1); 第二種計算方式(加權平均法,又稱期望): 1 (1/n+1)+1 (1/n+1)+...+1 (1/n+1)+n (1/(n+1))=1,所以加權平均時間複雜度為O(1);
第三種計算方式(均攤時間複雜度): 前n個操作複雜度都是O(1),第n+1次操作的複雜度是O(n),所以把最後一次的複雜度分攤到前n次上,那麼均攤下來每次 操作的複雜度為O(1)
八 練習題
特別注意 :len =10 ,並不是確定量,只是初始值而已
本例中資料規模的大小n 對應的含義還是 陣列的長度
(1)解析:
1 、 最好情況時間複雜度為 O(1)
2 、最壞時間複雜度為 O(n)
最壞情況程式碼執行的次數跟每次陣列的長度有關
第1次呼叫insert的執行的次數為 n ,
第2次呼叫insert的執行的次數為 2n ,
第3次呼叫insert的執行的次數為 2^2 * n
第k次呼叫insert的執行的次數為 2^(k-1) * n
最壞時間複雜度為 O(n)。
3 、平均時間複雜度O(1)
當每次遇到最壞情況時陣列會進行2倍擴容,原陣列被匯入新陣列,雖然陣列的長度變大了,但是插入操作落在的區間的長度是一樣的,分別是0~len-1, len~( 2len-1),....;
插入的情況仍是len+1種:0~len-1和插滿之後的O(len);所以每次插入的概率是:p= 1/len+1, 最後求出加權平均時間複雜度為 1 p + 2 p+ ▪▪▪ + len*p + len * p = O(1) ;
4、均攤時間複雜度 O(1)
均攤複雜度由於每次O(len)的出現都跟著len次O(1),是前後連貫的,因而將O(len)平攤到前len次上,得出平攤複雜度是O(1)
摘抄自 :王爭的資料結構與演算法之美
近期文章:
如果你喜歡本文
請長按二維碼,關注 喬志勇筆記