nlogn的算法有哪些,算法運行時間1、logN、N、NlogN 、N^2、N^3、2^n之間的比較
nlogn的算法有哪些,算法運行時間1、logN、N、NlogN 、N^2、N^3、2^n之間的比較
排序算法中,常常要求我們估算出最壞情況運行時間和平均情況/期望運行時間。在估算運行時間時,我們常用到下面一些時間量:
?1 | ?大部分程序的大部分指令之執行一次,或者最多幾次。如果一個程序的所有指令都具有這樣的性質,我們說這個程序的執行時間是常數。 |
?logN? | ?如果一個程序的運行時間是對數級的,則隨著N的增大程序會漸漸慢下來,如果一個程序將一個大的問題分解成一系列更小的問題,每一步都將問題的規 模縮減成幾分之一?,一般就會出現這樣的運行時間函數。在我們所關心的范圍內,可以認為運行時間小于一個大的常數。對數的基數會影響這個常數,但改變不會太 大:當N=1000時,如果基數是10,logN等于3;如果基數是2,logN約等于10.當N=1 00 000,logN只是前值的兩倍。當N時原來的兩倍,logN只增長了一個常數因子:僅當從N增長到N平方時,logN才會增長到原來的兩倍。 |
?N | ?如果程序的運行時間的線性的,很可能是這樣的情況:對每個輸入的元素都做了少量的處理。當N=1 000 000時,運行時間大概也就是這個數值;當N增長到原來的兩倍時,運行時間大概也增長到原來的兩倍。如果一個算法必須處理N個輸入(或者產生N個輸出), 那么這種情況是最優的。 |
?NlogN | ?如果某個算法將問題分解成更小的子問題,獨立地解決各個子問題,最后將結果綜合起來?(如歸并排序,堆排序),運行時間一般就是NlogN。我們找不到一個更好的形容, 就暫且將這樣的算法運行時間叫做NlogN。當N=1 000 000時,NlogN大約是20 000 000。當N增長到原來的兩倍,運行時間超過原來的兩倍,但超過不是太多。 |
? N平方 | ?如果一個算法的運行時間是二次的(quadratic),那么它一般只能用于一些規模較小的問題。這樣的運行時間通常存在于需要處理每一對輸入 數據項的算法(在程序中很可能表現為一個嵌套循環)中,當N=1000時,運行時間是1 000 000;如果N增長到原來的兩倍,則運行時間將增長到原來的四倍。 |
?N三次方 | ?類似的,如果一個算法需要處理輸入數據想的三元組(很可能表現為三重嵌套循環),其運行時間一般就是三次的,只能用于一些規模較小的問題。當N=100時,運行時間就是1 000 000;如果N增長到原來的兩倍,運行時間將會增長到原來的八倍。 |
?2的N次方 | ?如果一個算法的運行時間是指數級的(exponential),一般它很難在實踐中使用,即使這樣的算法通常是對問題的直接求解。當N=20時,運行時間是1 000 000;如果增長到原來的兩倍時,運行時間將是原時間的平方! |
nlogn的算法有哪些。?
常見排序算法運行時間比較:
運行小時數怎么計算、?
算法 | 最壞情況運行時間 | 平均情況/期望運行時間 |
插入算法 | O(n^2) | O(n^2) |
快速排序 | O(n^2) | O(nlogn)【期望】 |
歸并排序 | O(nlogn) | O(nlogn) |
堆排序 | O(nlogn) | O(1) |
希爾排序 | O(n^2) | O(n^(3/2)) |
桶排序 | O(n^2) | O(n)【平均情況】 |
?
1KB=2^10=1024
1MB=2^20=2^10*2^10=1024*1024約等于1 000 000(百萬)
1GB=2^30=2^10*2^10*2^10=1024*1024*1024約等于1 000 000 000 (十億)