程序段的時間復雜度怎么算？

當輸入量n逐漸加大時，時間復雜性的極限情形稱為算法的“漸近時間復雜性”。

我們常用大O表示法表示時間復雜性，注意它是某一個算法的時間復雜性。大O表示只是說有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個上界，但并不是上確界，但人們在表示的時候一般都習慣表示前者。

此外，一個問題本身也有它的復雜性，如果某個算法的復雜性到達了這個問題復雜性的下界，那就稱這樣的算法是 最佳算法。

“大O記法”：在這種描述中使用的基本參數是

n，即問題實例的規模，把復雜性或運行時間表達為n的函數。這里的“O”表示量級 (order)，比如說“二分檢索是 O(logn)的”,也就是說它需要“通過logn量級的步驟去檢索一個規模為n的數組”記法 O ( f(n) )表示當 n增大時，運行時間至多將以正比于 f(n)的速度增長。

這種漸進估計對算法的理論分析和大致比較是非常有價值的，但在實踐中細節也可能造成差異。例如，一個低附加代價的O(n2)算法在n較小的情況下可能比一個高附加代價的 O(nlogn)算法運行得更快。當然，隨著n足夠大以后，具有較慢上升函數的算法必然工作得更快。