《算法技術手冊》一2.4 性能名額

在比較算法時，我們使用了問題資料的規模n來評估算法的性能。這是過去半個世紀算法比較的标準方法。通過輸入資料的規模評估算法的執行時間，我們可以知曉哪種算法能夠更好地适應一些異正常模的問題。性能評估的第二種方法是考慮算法将會耗費多少記憶體或者存儲空間。之後的小節詳細讨論這個問題。

常見的算法分類（按照效率降序排列）如下：

常數級：O(1)

對數級：O(log n)

次線性級：O(nd)，其中d < 1

線性級：O(n)

線性對數級：O(n log n)

平方級: O(n2)

指數級：O(2n)

注意：在評估算法性能時，必須要找到算法中計算費用最大的部分才能決定算法的分類。例如，如果一個算法可以被劃分為兩個任務，其中一個任務為線性級，另一個任務為平方級，那麼這個算法的總體性能應當歸為平方級。

下面将通過一些例子來闡釋這些不同的性能分類。