有木有人跟我一樣，看到復(fù)雜度三個(gè)字，能熟練說出常見算法的時(shí)間復(fù)雜度，但潛臺(tái)詞：“誒？怎么算來著？怎么算來著？”。

簡介

百度百科如下定義時(shí)間復(fù)雜度：

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得T(n)/f(n)的極限值（當(dāng)n趨近于無窮大時(shí)）為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))，稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。

也就是說隨著n的增大，算法執(zhí)行的時(shí)間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。

計(jì)算方法

用大寫O()來體現(xiàn)算法時(shí)間復(fù)雜度的記法，我們稱之為大O記法，推導(dǎo)方法如下：

1. 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)；
2. 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)；
3. 如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)，得到的結(jié)果就是大O階。

常數(shù)階：O(1)；
線性階：O(n);
對(duì)數(shù)階：O(logn)；
平方階：O(n^2)；
O(1) 常數(shù)階 < O(logn) 對(duì)數(shù)階 < O(n) 線性階 < O(nlogn) < O(n^2) 平方階 < O(n^3) < O(2^n) < O(n!) < O(n^n)

示例

• 舉個(gè)對(duì)數(shù)階的??

int count = 1;      
while (count < n)
{
   count = count * 2;
}

有多少個(gè)2相乘后大于n，則會(huì)退出循環(huán)，設(shè)循環(huán)次數(shù)為x，n = 2^x，得到x = logn，所以這個(gè)算法的時(shí)間復(fù)雜度為O(logn)。

• 再舉個(gè)平方階的??

for (NSUInteger i = 0; i < array.count; i++)
{
      for (NSUInteger j = 0; j < array.count-1-i; j++)
      {
           if ([array[j] floatValue] > [array[j+1] floatValue])
           {
               [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
           }
      }
 }

• 最后一個(gè)??

//執(zhí)行1次 
int i, sum = 0, n = 100;    
// 執(zhí)行 n+1 次
for( i = 1; i <= n; i++)    
{
   //執(zhí)行n次
    sum = sum + i;          
}   

根據(jù)注釋可得到，該算法執(zhí)行的總次數(shù)為：1+(n+1)+n=2n+2，根據(jù)大O記法推導(dǎo)：
第一步用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)，得到2n+1;
第二步保留最高階項(xiàng)，得到2n;
第三步如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)，得到該算法的時(shí)間復(fù)雜度為O(n)。