複雜度分析-演算法學習的精髓
我們知道學習資料結構與演算法主要是解決一個「快」和「省」的問題,如何讓程式碼執行更快、如何更節省空間。那麼如何來考量你的程式碼的執行效率呢,我們總要有一個標準,這就是我今天所講的複雜度分析,不誇張的說,掌握好複雜度分析,資料結構與演算法你就掌握了一半,所有的演算法都逃不出複雜度分析的範疇。
複雜度分析包括時間複雜度和空間複雜度。
如何考量我們程式碼的執行效率,有的人可能會說我在計算機上跑一下不得了,簡單便捷,沒錯,這樣確實可以。但是這種方法太依賴硬體環境了,你在不同的機器上跑的時間肯定是不一樣的。所以,我們需要一種不依靠測試環境,不需要測試資料的方法來估計演算法的執行效率的方法。 大 O 時間複雜度上場了。
大 O 複雜度表示法
直接上程式碼,我會帶你一起來估算程式碼的執行時間,在實戰中掌握大 O 複雜度。
int sum(int n) { int sum = 0; int i = 1; for(; i<=n; i++) { sum = sum + i; } return sum; }
上面是一個計算從 1 + 2 + 3 + ··· + n 的求和,我們假設每行程式碼的執行時間都是一個 unit_time。我們可以看到第 3、4 行的程式碼都運行了 1 個 unit_time,第 6、8 行都運行了 n 個 unit_time。所以這段程式碼執行時間為 T(n) = (2n+2) * unit_time。即 T(n) = O(2n+2), 這就是大 O 時間複雜度表示法。 當 n 趨向於無窮大時,記為 T(n) = O(n)。
大 O 時間複雜度表示法實際上並不表示程式碼真正的執行時間,大家也看到了,T(n)才是程式碼真正的執行時間,大 O 時間複雜度是表示程式碼執行時間隨資料規模增長的變化趨勢 。
演算法的時間複雜度採用這種數量級的形式表示後,將給分析演算法的時間複雜度帶來很大的方便。即對一個演算法,只需分析影響該演算法時間複雜度的主要部分即可,而無需對該演算法的每一個語句都進行纖細的分析。
時間複雜度分析
那麼問題來了,給我們一段程式碼,我們怎麼分析它的時間複雜度呢?我有二個實操的方法可以分享給你。
1. 關注執行次數最多的一段程式碼
在上面那個例子中,執行次數最多的是第 6、8 行,所以總的時間複雜度就是 O(n)。
2. 關注量級最大的那段程式碼
看下面程式碼,你可以先試著分析一下,再往下翻。
int sum(int n) { int sum_1 = 0; int x = 1; for(; p< 10; p++) { sum_1 += p; } int sum_2 = 0; int q = 1; for(; q< n; q++) { sum_2 += q; } int sum_3 = 0; int i = 1; for(; i<=n; i++) { int j = 1; for(; j<=n; j++) { sum_3 = sum_3 + i *j; } } return sum_1 + sum_2+ sum_3; }
第一段執行了 10 次,這是一個常量的執行時間,跟 n 的規模無關,就算它執行一百次、一千次,它也是常量級的執行時間。所以為 O(1)。
第二段和第三段程式碼分別為 O(n)、O(n2 ),這對你應該不是很難。所以我們只關注量級最大的程式碼的時間複雜度,即 O(n2 )。
大 O 表示法有乘法法則和加法法則,非常好理解,乘法法則實際上就是巢狀迴圈 。相信你已經懂了時間複雜度的大 O 分析法了。
下面我介紹一些常見的時間複雜度分析例項。
(敲黑板,劃重點了,拿小本本記下)
1. O(1)
O(1) 常量級時間複雜度
int x = 1; int y = 2; int sum = x + y;
1. O(logn)
i = 1; while( i <= n) { i = i * 2; }
程式碼的執行次數為 x = log2 n,即求解方程 2x = n。
複雜度分析並不難,關鍵在於多練(感覺)。只要跟著我的思路學習、練習,很快,你看到程式碼,簡單的你能一眼看出複雜度,難的你也不會畏懼,分析一下就出來了。