目錄
- 時間複雜度
- 常用資料結構操作與算法的複雜度
- 輸入規模較小時的情況
- 引用
部落格：blog.shinelee.me | 部落格園 | CSDN
如何評估一個算法的計算時間？
一個算法的實際運作時間很難評估，當時的輸入、CPU主頻、記憶體、資料傳輸速度、是否有其他程式在搶占資源等等，這些因素都會影響算法的實際運作時間。為了公平地對比不同算法的效率，需要脫離開這些實體條件，抽象出一個數學描述。在所有這些因素中，問題的規模往往是決定算法時間的最主要因素。是以，定義算法的時間複雜度\(T(n)\)，用來描述算法的執行時間随着輸入規模的增長将如何變化，增長速度是怎樣的。
在輸入規模較小時，運作時間本來就少，不同算法的差異不大。是以，時間複雜度通常關注的是輸入規模\(n\)較大時運作時間的變化趨勢，稱之為漸進複雜度，采用大O記号，表示漸進上界，對于任意的\(n >> 2\)，若有常數\(c\)和函數\(f(n)\)滿足
\[T(n) \leq c \cdot f(n)
\]
則記作
\[T(n) = O(f(n))
可以簡單地認為，\(O(f(n))\)表示運作時間與\(f(n)\)成正比，比如\(O(n^2)\)表示運作時間與輸入規模的平方成正比，這樣講雖然并不嚴謹，但一般情況下無傷大雅。
在\(n\)很大時，常數\(c\)變得無關緊要，不同算法間的比較主要關注\(f(n)\)部分的大小。比如，在\(n >> 100\)時，\(n^2\)要比\(100n\)大得多，是以重點關注\(n^2\)和\(n\)增長速度的差異即可。
不同時間複雜度的增長速度對比如下，圖檔來自Big-O Cheat Sheet Poster，
除了大\(O\)記号，還有大\(\Omega\)記号和\(\Theta\)記号，分别表示下界和确界，
\[\Omega(f(n)) : \ c\cdot f(n) \leq T(n) \\\Theta(f(n)) : \ c_1 \cdot f(n) \leq T(n) \leq c_2 \cdot f(n)
他們的關系如下圖所示，圖檔截自鄧俊輝-資料結構C++描述第三版
下面彙總摘錄了常用資料結構操作和排序算法的複雜度，來源見引用。其中包含最壞時間複雜度、平均時間複雜度以及空間複雜度等，對于排序算法還含有最好時間複雜度。
附帶上連結：
Array Stack Queue Singly-Linked List Doubly-Linked List Skip List Hash Table Binary Search Tree Cartesian Tree B-Tree Red-Black Tree Splay Tree AVL Tree KD Tree
Quicksort Mergesort Timsort Heapsort Bubble Sort Insertion Sort Selection Sort Tree Sort Shell Sort Bucket Sort Radix Sort Counting Sort Cubesort
以及 Data Structures in geeksforgeeks。
漸進複雜度分析的是輸入規模較大時的情況，輸入規模較小時呢？
在輸入規模較小時，就不能輕易地忽略掉常數\(c\)的作用，如下圖所示，圖檔來自Growth Rates Review。複雜度增長快的在輸入規模較小時可能會小于複雜度增長慢的。
是以在選擇算法時，不能無腦上看起來更快的進階資料結構和算法，還得具體問題具體分析，因為進階資料結構和算法在實作時往往附帶額外的計算開銷，如果其帶來的增益無法抵消掉隐含的代價，可能就會得不償失。
這同時也給了我們在代碼優化方向上的啟示，
- 一是從\(f(n)\)上進行優化，比如使用更進階的算法和資料結構；
- 還有是對常數\(c\)進行優化，比如移除循環體中不必要的索引計算、重複計算等。
以上
- Big-O Cheat Sheet Poster
- Know Thy Complexities
- 鄧俊輝-資料結構C++描述第三版
- Growth Rates Review