漸進時間複雜度

漸進時間複雜度

漸進時間複雜度是指對於一個算法來說,我們常常需要計算其複雜度來決定我們是否選擇使用該算法。

基本信息

定義

對於一個算法,假設其問題的輸入大小為n,那么我們可以用 O(n) 來表示其算法複雜度(time complexity)。那么,漸進時間複雜度(asymptotic time complexity)就是當n趨於無窮大的時候,O(n)得到的極限值。

可以理解為:我們通過計算得出一個算法的運行時間 T(n), 與T(n)同數量級的即冪次最高的O(F(n))即為這個算法的時間複雜度。例如:某算法的運行時間T(n) = n+10與n是同階的(同數量級的),所以稱T(n)=O(n)為該算法的時間複雜度。

算法的漸進分析就是要估計:n逐步增大時資源開銷T(n)的增長趨勢。

相關詞條

相關搜尋

熱門詞條

聯絡我們