1、算法時間複雜度含義？
2、什麼是logN?
3、算法時間複雜度的不同度量
3.1 常數階O(1)
3.2 對數階O(log2n)
3.3 線性階O(n)
3.4 線性對數階O(nlog2n)
3.5 平方階O(n^2)
3.6 立方階O(n^3)
3.7 指數階（又叫2的N次方）O(2^n)
4、排序算法的時間複雜度
1、算法時間複雜度含義？
1.1 算法複雜度
算法複雜度是指算法在編寫成可執行程序後，運行時所需要的資源，資源包括時間資源和內存資源。應用於數學和計算機導論。
算法複雜度包含兩個方面：
- 時間複雜度
- 空間複雜度
1.2 時間頻度
- 一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。
- 但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。
- 並且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。
- 一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。算法的時間複雜度是指執行算法所需要的計算工作量。
1.3 時間複雜度
- 在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間複雜度概念。
- 一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),存在一個正常數c使得fn*c>=T(n)恆成立。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。
2、什麼是logN?
對數函數：
- 對數函數是以冪（真數）為自變量，指數為因變量，底數為常量的函數。
- 如果ax =N（a>0，且a≠1），那麼數x叫做以a為底N的對數，記作x=logaN，讀作以a為底N的對數，其中a叫做對數的底數，N叫做真數。
- 一般地，函數y=logaX（a>0，且a≠1）叫做對數函數，也就是說以冪（真數）為自變量，指數為因變量，底數為常量的函數，叫對數函數。其中x是自變量，函數的定義域是（0，+∞），即x>0。它實際上就是指數函數的反函數，可表示為x=ay。因此指數函數里對於a的規定，同樣適用於對數函數。
算法中的logN：
算法分析中logN沒有特殊說明應該是默認2為底,因為以2為底的log函數的相對增長率要大於其他底數情況（如底數為3,4,5……）.作為對時間複雜度的估計,底數為2的O(logN)可以看做是log函數型相對增長率的上界
3、算法時間複雜度的不同度量
在各種不同算法中，若算法中語句執行次數為一個常數，則時間複雜度為O(1),另外，在時間頻度不相同時，時間複雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時間複雜度相同，都為O(n^2)。
按數量級遞增排列，常見的時間複雜度有：
- 常數階O(1)
- 對數階O(log2n)(以2為底n的對數，下同)
- 線性階O(n)
- 線性對數階O(nlog2n)
- 平方階O(n^2)
- 立方階O(n^3),...，
- k次方階O(n^k)
- 指數階O(2^n)。
隨著問題規模n的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低。
3.1 常數階O(1)
大部分程序的大部分指令之執行一次，或者最多幾次。如果一個程序的所有指令都具有這樣的性質，我們說這個程序的執行時間是常數。
3.2 對數階O(log2n)
如果一個程序的運行時間是對數級的，則隨著N的增大程序會漸漸慢下來，如果一個程序將一個大的問題分解成一系列更小的問題，每一步都將問題的規 模縮減成幾分之一 ，一般就會出現這樣的運行時間函數。在我們所關心的範圍內，可以認為運行時間小於一個大的常數。對數的基數會影響這個常數，但改變不會太 大：當N=1000時，如果基數是10，logN等於3；如果基數是2，logN約等於10.當N=1 00 000，logN只是前值的兩倍。當N時原來的兩倍，logN只增長了一個常數因子：僅當從N增長到N平方時，logN才會增長到原來的兩倍。
3.3 線性階O(n)
如果程序的運行時間的線性的，很可能是這樣的情況：對每個輸入的元素都做了少量的處理。當N=1 000 000時，運行時間大概也就是這個數值；當N增長到原來的兩倍時，運行時間大概也增長到原來的兩倍。如果一個算法必須處理N個輸入（或者產生N個輸出）， 那麼這種情況是最優的。
3.4 線性對數階O(nlog2n)
如果某個算法將問題分解成更小的子問題，獨立地解決各個子問題，最後將結果綜合起來 （如歸併排序，堆排序），運行時間一般就是NlogN。我們找不到一個更好的形容， 就暫且將這樣的算法運行時間叫做NlogN。當N=1 000 000時，NlogN大約是20 000 000。當N增長到原來的兩倍，運行時間超過原來的兩倍，但超過不是太多。
3.5 平方階O(n^2)
如果一個算法的運行時間是二次的（quadratic），那麼它一般只能用於一些規模較小的問題。這樣的運行時間通常存在於需要處理每一對輸入 數據項的算法（在程序中很可能表現為一個嵌套循環）中，當N=1000時，運行時間是1 000 000；如果N增長到原來的兩倍，則運行時間將增長到原來的四倍。
3.6 立方階O(n^3)
類似的，如果一個算法需要處理輸入數據想的三元組（很可能表現為三重嵌套循環），其運行時間一般就是三次的，只能用於一些規模較小的問題。當N=100時，運行時間就是1 000 000；如果N增長到原來的兩倍，運行時間將會增長到原來的八倍。
3.7 指數階（又叫2的N次方）O(2^n)
如果一個算法的運行時間是指數級的（exponential），一般它很難在實踐中使用，即使這樣的算法通常是對問題的直接求解。當N=20時，運行時間是1 000 000；如果增長到原來的兩倍時，運行時間將是原時間的平方！
4. 排序算法的時間複雜度
排序算法的時間複雜度對比
