# 複雜度 ## 12/15社課 --- ### 複雜度是啥 簡單來說就是 程式的好壞程度的量化 基本上以使用的時間和空間來作為標準 ---- ### 為什麼需要複雜度 如果你不希望寫出來的程式出現TLE ~~尤其是檢定剩5分鐘的情況下~~ 那就得在寫程式前評估做法 ---- ### 複雜度的概念 一次函數vs二次函數 y=x+10 、 y=x^2 在數字很大的時候 右式會大於左式很多 以多次執行而言 左式比較容易(量級低) ---- ### 量級 對於兩個數學式的比較而言 如果一個數學式的成長幅度較大(ex:曲線幅度) 則此數學式的量級較大 [參考圖](https://hackmd.io/_uploads/rkYPVT_Lp.png) --- ### 時間複雜度 指完全地執行程式所需的時間 通常以執行次數計算 ~~也就是萬惡TLE的根源~~ 表達方式為 Big O ---- ### 時間複雜度的表達 如果執行次數固定 不會因為輸入值而改變 這種情況被寫作 O(1) ```cpp= cin >> a; cout << a;//這裡只固定執行一次! ``` ---- O(n) 和 O(n^2) 如下 ```cpp= for(i=0;i<n;i++){ cout << i; } //O(n) for(i=0;i<n;i++){ for(i=0;i<n-1;i++){ //這裡執行了n*(n-1)次 cout << i; } } //O(n^2) ``` 時間複雜度取最高次方 其他 O(n log(n)) O(n^3) 只要大致上數迴圈數量就行 ---- ### 時間複雜度的計算 以最糟情況做計算 只考慮最高次方 省略係數 ---- 假設OJ 1秒能跑10^8次運算 把題目的n範圍帶入估算複雜度 並除以10^8 就能大致推算秒數 ---- Example: 1 < n < 5×10^5 ,O(n^2) 5×10^5 的平方除以10^8就是秒數 ---- 函數的複雜度不是只有O(1) 使用函數的時候要清楚它的執行時間 (像vector 的 insert() 和 erase()都不是O(1) ! ) ---- 另外 在函數中傳遞一個很大的物件時 由於函數的傳遞視作把整個物件複製一次 所以複雜度並不是O(1) --- ### 空間複雜度 字面上翻譯就是使用的空間量 也就是記憶體用量 表達方式也是 Big O ---- 這裡的變數使用量是固定不變的 記作O(1) ```cpp= cin >> n; for(int i=0;i<n;i++){ cout<<i; } ``` ---- 這裡的變數用量會隨輸入大小而增加 記作O(n) ```cpp= cin >> n; int A[n]; for(int i=0;i<n;i++){ A[n] = i; } ``` --- 時間和空間複雜度是能互相交換的 可以透過較多的記憶體用量換取時間 也就是 ~~以空間換時間~~ 如泡沫排序(時間久) 桶排序(記憶體用量大) 可以視情況使用適合的演算法 ---- 練習 [c296](https://zerojudge.tw/ShowProblem?problemid=c296)