時間復(fù)雜度排序：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)

時間復(fù)雜度排序（來源見水印）

常見時間復(fù)雜度

f(n)=1時，時間復(fù)雜度為O(1)，可以稱為常數(shù)階。
f(n)=logn時，時間復(fù)雜度為O(logn)，可以稱為對數(shù)階。
f(n)=n時，時間復(fù)雜度為O(n)，可以稱為線性階。
f(n)=n2時，時間復(fù)雜度為O(n2)，可以稱為平方階。

除了常數(shù)階、線性階、平方階、對數(shù)階，還有如下時間復(fù)雜度：

f(n)=nlogn時，時間復(fù)雜度為O(nlogn)，可以稱為nlogn階。
f(n)=n3時，時間復(fù)雜度為O(n3)，可以稱為立方階。
f(n)=2?時，時間復(fù)雜度為O(2?)，可以稱為指數(shù)階。
f(n)=n!時，時間復(fù)雜度為O(n!)，可以稱為階乘階。
f(n)=(√n時，時間復(fù)雜度為O(√n)，可以稱為平方根階。

算法的效率

時間復(fù)雜度：評估執(zhí)行程序所需的時間。可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?br> 空間復(fù)雜度：評估執(zhí)行程序所需的存儲空間?？梢怨浪愠龀绦?qū)τ嬎銠C(jī)內(nèi)存的使用程度。

設(shè)計算法時，一般是要先考慮系統(tǒng)環(huán)境，然后權(quán)衡時間復(fù)雜度和空間復(fù)雜度，選取一個平衡點。不過，時間復(fù)雜度要比空間復(fù)雜度更容易產(chǎn)生問題，因此算法研究的主要也是時間復(fù)雜度，不特別說明的情況下，復(fù)雜度就是指時間復(fù)雜度。

時間復(fù)雜度

時間頻度
一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機(jī)運行測試才能知道。但我們不可能也沒有必要對每個算法都上機(jī)測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。

時間復(fù)雜度
前面提到的時間頻度T(n)中，n稱為問題的規(guī)模，當(dāng)n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律，為此我們引入時間復(fù)雜度的概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)，記作T(n)=O(f(n))，它稱為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。

大O表示法

像前面用O( )來體現(xiàn)算法時間復(fù)雜度的記法，我們稱之為大O表示法。
算法復(fù)雜度可以從最理想情況、平均情況和最壞情況三個角度來評估，由于平均情況大多和最壞情況持平，而且評估最壞情況也可以避免后顧之憂，因此一般情況下，我們設(shè)計算法時都要直接估算最壞情況的復(fù)雜度。
大O表示法O(f(n)中的f(n)的值可以為1、n、logn、n2等，因此我們可以將O(1)、O(n)、O(logn)、O(n2)分別可以稱為常數(shù)階、線性階、對數(shù)階和平方階，那么如何推導(dǎo)出f(n)的值呢？我們接著來看推導(dǎo)大O階的方法。

推導(dǎo)大O階

推導(dǎo)大O階，我們可以按照如下的規(guī)則來進(jìn)行推導(dǎo)，得到的結(jié)果就是大O表示法：
1.用常數(shù)1來取代運行時間中所有加法常數(shù)。
2.修改后的運行次數(shù)函數(shù)中，只保留最高階項
3.如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。

1. 常數(shù)階
   先舉個例子，如下所示。

  int sum = 0,n = 100; //執(zhí)行一次  
  sum = (1+n)*n/2; //執(zhí)行一次  
  System.out.println (sum); //執(zhí)行一次 

上面算法的運行的次數(shù)的函數(shù)為f(n)=3，根據(jù)推導(dǎo)大O階的規(guī)則1，我們需要將常數(shù)3改為1，則這個算法的時間復(fù)雜度為O(1)。如果sum = （1+n）*n/2這條語句再執(zhí)行10遍，因為這與問題大小n的值并沒有關(guān)系，所以這個算法的時間復(fù)雜度仍舊是O(1)，我們可以稱之為常數(shù)階。

2. 線性階
   線性階主要要分析循環(huán)結(jié)構(gòu)的運行情況，如下所示。

for(int i=0;i<n;i++){
//時間復(fù)雜度為O(1)的算法
...
}

上面算法循環(huán)體中的代碼執(zhí)行了n次，因此時間復(fù)雜度為O(n)。

3. 對數(shù)階
   接著看如下代碼：

int number=1;
while(number<n){
number=number*2;
//時間復(fù)雜度為O(1)的算法
...
}

可以看出上面的代碼，隨著number每次乘以2后，都會越來越接近n，當(dāng)number不小于n時就會退出循環(huán)。假設(shè)循環(huán)的次數(shù)為X，則由2^x=n得出x=log?n，因此得出這個算法的時間復(fù)雜度為O(logn)。

4. 平方階
   下面的代碼是循環(huán)嵌套：

  for(int i=0;i<n;i++){   
      for(int j=0;j<n;i++){
         //復(fù)雜度為O(1)的算法
         ... 
      }
  }

內(nèi)層循環(huán)的時間復(fù)雜度在講到線性階時就已經(jīng)得知是O(n)，現(xiàn)在經(jīng)過外層循環(huán)n次，那么這段算法的時間復(fù)雜度則為O(n2)。
接下來我們來算一下下面算法的時間復(fù)雜度：

  for(int i=0;i<n;i++){   
      for(int j=i;j<n;i++){
         //復(fù)雜度為O(1)的算法
         ... 
      }
  }

需要注意的是內(nèi)循環(huán)中int j=i，而不是int j=0。當(dāng)i=0時，內(nèi)循環(huán)執(zhí)行了n次；i=1時內(nèi)循環(huán)執(zhí)行了n-1次，當(dāng)i=n-1時執(zhí)行了1次，我們可以推算出總的執(zhí)行次數(shù)為：

n+(n-1)+(n-2)+(n-3)+……+1
=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……
=(n+1)+(n+1)+(n+1)+(n+1)+……
=(n+1)n/2
=n(n+1)/2
=n2/2+n/2

根據(jù)此前講過的推導(dǎo)大O階的規(guī)則的第二條：只保留最高階，因此保留n2/2。根據(jù)第三條去掉和這個項的常數(shù)，則去掉1/2,最終這段代碼的時間復(fù)雜度為O(n2)。

ps:
冒泡排序的時間復(fù)雜度，最壞情況下為O(n2)，最好情況O(n)。
選擇排序的時間復(fù)雜度，無論什么數(shù)據(jù)進(jìn)去都是O(n2)的時間復(fù)雜度。
十大經(jīng)典排序算法（動圖演示）
常見排序算法及其對應(yīng)的時間復(fù)雜度和空間復(fù)雜度