算法效率的度量與漸進分析


對於一個算法的運行時間,通常不能采用時間的長短來衡量,因為算法的運行時間的長短依賴於輸入數據的情況。


算法的運行時間可以分為最差運行時間和平均運行時間。平均運行時間需要考慮所有的情況,因此相對麻煩,不實用。所以,通常采用最差運行時間來衡量算法的好壞。

算法的最差運行時間是一個界限,但這並不意味著一定存在某個具體的例子達到這一界限,它有可能不緊致,還有進一步提升的空間。


下表顯示瞭常見的算法復雜度與時間的關系:



可以觀察出,多項式時間和指數時間的差別還是很大的。


在算法效率度量中,常常采用漸進表達式,因為常數間的差異較小,漸進表達式的核心就是忽略常數。


漸進分析常用的符號有:





舉例說明如下:

f(n) = 32n2 + 17n + 32.

f(n) 屬於 O(n2), O(n3), (n2), (n), and (n2) .

f(n) 不屬於 O(n), (n3), (n), or (n3).

0 個評論

要回覆文章請先登錄註冊