算法運作時間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；如果增長到原來的兩倍時，運作時間将是原時間的平方！

常見排序算法運作時間比較：

算法	最壞情況運作時間	平均情況/期望運作時間
插入算法	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 (十億)