表示時間的大O符號，是用來描述演算法效率的語言和度量單位。不徹底理解這個概念，不僅會影響你做出清晰的判斷，還會讓你無法評價演算法的優劣。 常量不算在運算時間里。 例如某個O(2N)的演算法實際上是O(N)。特定輸入中，O(N)很有可能會比O(1)代碼還要快。大O僅僅描述了增長的趨勢。 丟棄不重要的項 應該 ...
表示時間的大O符號，是用來描述演算法效率的語言和度量單位。不徹底理解這個概念，不僅會影響你做出清晰的判斷，還會讓你無法評價演算法的優劣。
- 常量不算在運算時間里。
例如某個O(2N)的演算法實際上是O(N)。特定輸入中，O(N)很有可能會比O(1)代碼還要快。大O僅僅描述了增長的趨勢。
- 丟棄不重要的項
應該捨棄無關緊要的項。比如 O(N2+N)變成O(N2)、O(N+logN)變成O(N)、O(5*2^N+1000N^100)變成O(2^N)等。
- logN運行時間
元素的個數每次減半，它的運行時間很可能是O(logN)。
以二分查找為例。假設一個排序數組長度為N，目標值為x。首先比較x與中值，如果x等於中值直接返回，如果小於中值，搜索數組的左邊，如果大於中值，搜索數組的右邊。
開始時有N個元素的排序數組要搜索，經過一次搜索之後，還剩下N/2個元素，再一次，剩下N/4個元素，直到找到目標值或者待搜索元素個數為1時才停止搜索。
同理，在平衡二叉搜索樹中查找一個元素也是O(logN)，每次比較，非左即右。
- 遞歸的運行時間
當一個多次調用自己的遞歸函數出現時，它的運行時間往往是O(分支數^數的深度)，分支數即每次調用自己的次數。
例如：
int f(int n) { if (n <= 1) { return 1; } return f(n-1) + f(n-1); }
運行時間是O(2^N)。
這個例子的空間複雜度為O(N)，儘管樹節點總數為O(2^N)，但同一時刻只有O(N)個節點存在。
再例如：
把平衡二叉搜索樹上所有節點的值相加，運行時間是多少？
分支樹是2，深度大概是logN，所以為O(2^logN) = O(N) , 運行時間是O(N)。
