時間與空間複雜度

--- title : 時間與空間複雜度 tags : article --- # 時間與空間複雜度 ### 程式解題時的一些常用術語 | short | full-name | | | ----- | ------------------- | ---------- | | AC | Accept | 答案正確 | | WA | Wrong Answer | 答案錯誤 | | TLE | Time Limit Exceed | 超時 | | MLE | Memory Limit Exceed | 記憶體超量 | | RE | Runtime Error | 執行錯誤 | | CE | Compile Error | 編譯錯誤 | --- ### 程式的執行時間分析電腦每秒可以執行多少次，取決於CPU，以i7-10代的電腦來說，其CPU平均執行速度為2.53GHz ~ 5GHz (GHz = $10^9$ proces. per second) 而我們通常評估程式的時候，都會以 $10^8$~$10^9$ 來衡量，此數值意義是代表每秒可以執行幾次，也就是你評估出當前題目的時間複雜度會超過這個數值時，就可能會TLE。 --- ### 程式的記憶體分析對於一個程式的記憶體用量，取決於當前程式所佔用的記憶體最大值，而對於大部分的程式片段來說，其記憶體上限為 4GB (4 Giga-Bytes)。 > 在電腦算數中 $\text{1K} = 2^{10} \approx 10^3, \text{1M} = 2^{20} \approx 10^6, \text{1G} = 2^{30} \approx 10^9$ ![](https://i.imgur.com/BVZ8Jnc.png) > 請務必牢記以上的紅色數字 > 以上這些知識在大三的演算法分析時會有更詳細的教學 --- ### Big-O 表示法其記錄數值的方式，便是用一個字母「O」的函式形式做表達，其表示法常會省略掉 係數、常數項、低次項 的部分，以下舉例： `ex.` $50n$ $⇒ O(n)$ `ex.` $7n^2+3n+1$ $⇒ O(n^2)$ `ex.` $10⋅(\log_2n)^3 + 1000⋅\log_2n$ $⇒ O(\log^3n)$ `ex.` $\sqrt{n}+(\log_2n)^3+\log_2n$ $⇒ O(\sqrt n)$ (請注意，log函式的省略底數格式，在電腦時間分析相關部分，其底數通常為2) ![](https://i.imgur.com/O58Qvwo.png =65%x) | | $n=10$ | $n=100$ | $n=10^4$ | $n=10^8$ | $n=10^{16}$ | | ----------- | --------- | --------- | --------- | --------- | ----------- | | $n!$ | 3628800 | 9.33e+157 | | | | | $2^n$ | 1024 | 1.267e+30 | 1.9e+3010 | 3e+3e+7 | 1e+3e+15 | | $n^2$ | 100 | 10000 | 1e+8 | 1e+16 | 1e+32 | | $n\log_2 n$ | 33.219280 | 664.38561 | 132877.12 | 2.6575e+9 | 5.315e+17 | | $n$ | 10 | 100 | 10000 | 1e+8 | 1e+16 | | $\sqrt n$ | 3.1622776 | 10 | 100 | 1000 | 1e+8 | | $\log_2 n$ | 3.3219280 | 6.6438561 | 13.287712 | 26.575424 | 53.150849 | (紅色部分是超過 $10^8$ 的數值) --- ### 時間複雜度(Time Complexity) 一個程式，或是一個演算法的時間效率，通常會記做「時間複雜度(Time Complexity)」，常以 **Big-O** 來表示，以下舉例： ```cpp int total = 0; for(int x = 0 ; x<N ; x++) total += total + x; // 單迴圈，計算二階差級數和 // Time Complexity : O(N) ``` ```cpp int m[N][N]; for(int x = 0 ; x<N ; x++){ for(int y = 0 ; y<N ; y++) cout << m[x][y] << ' '; cout << '\n'; } // 雙迴圈，印出 N×N 的陣列 // Time Complexity : O(N^2) ``` ```cpp for(int x = 0 ; x<N ; x++){ for(int y = 0 ; y<N ; y++); for(int z = 0 ; z<M ; z++); } // 複合雙迴圈， // Time Complexity : O(N(N+M)) ``` ```cpp void run(int n){ if(n) run(n-1); } // 遞迴 // Time Complexity : O(N) ``` ```cpp void run(int n){ if(n) run(n>>1); // n>>1 == n/2 } // 二分遞迴 // Space Complexity : O(logN) ``` --- ### 空間複雜度(Space Complexity) 一個程式，或是一個演算法的(記憶體)空間用量，通常會記做「空間複雜度(Space Complexity)」，也可使用 **Big-O** 來表示，以下舉例： ```cpp int arr[N][M]; // 二維陣列 // Space Complexity : O(NM) = NM bytes ``` ```cpp int SumOfRange(int L, int R){ if(L>R) return 0; return L + SumOfRange(L+1,R); } // 遞迴形式的區間和 (N = R-L) // Time Complexity : O(N) // Space Complexity : O(N) // Max-Memory Usage : 8N bytes ``` ```cpp int binary_search(int*arr, int L, int R, int tar){ if(L>=R) return arr[L] == tar ? L : -1; int mid = (L+R)/2; if(tar > arr[mid]) return binary_search(arr,mid+1,R,tar); else return binary_search(arr,L,mid-1,tar); } // 遞迴版的二分搜尋法，N為陣列arr的長度 = R - L // Time Complexity : O(logN) // Space Complexity : O(logN) // Max-Memory Usage : 20logN bytes ``` ```cpp int arr[100]; int L = 0, R = 100, tar, mid; while(L<R){ mid = (L+R)/2; if(tar > arr[mid]) L = mid+1; else R = mid-1; } // 迴圈版的二分搜尋法，N為陣列arr的長度 // Time Complexity : O(logN) // Space Complexity : O(1) // Max-Memory Usage : 416 bytes ``` 請注意，一段程式區段(scope`{}`)執行完後，裡面所宣告的所以變數都會被釋放(包含指標變數)，但被 new 的物件並不會被釋放，這些被 new 的物件必須要被 delete 後才會被釋放。而記錄一個程式的空間複雜度，我們會用整個程式最大會一次占用多少記憶體來記錄。 > 通常紀錄程式的空間複雜度，不太會用Big-O表示，因為其很容易計算也很容易過量使用。 > <友善提醒> 請務必注重 O(logN)算法 的潛力，其執行時間遠快於其他任何的執行時間。也因此，有一句話是這樣說的：「高階的程式設計應當避免使用迴圈」