姿势 | 小课堂：时间复杂度

有木有人跟我一样，看到复杂度三个字，能熟练说出常见算法的时间复杂度，但潜台词：“诶？怎么算来着？怎么算来着？”。

为了以后不再一脸懵逼二脸懵逼对角线懵逼，小豆就写了这篇小笔记。
参考链接：https://blog.csdn.net/daijin888888/article/details/66970902

简介

百度百科如下定义时间复杂度：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

也就是说随着n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。

计算方法

用大写O()来体现算法时间复杂度的记法，我们称之为大O记法，推导方法如下：

1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数函数中，只保留最高阶项；
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。

常数阶：O(1)；
线性阶：O(n);
对数阶：O(logn)；
平方阶：O(n^2)；
O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < O(2^n) < O(n!) < O(n^n)

示例

• 举个对数阶的🌰

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

有多少个2相乘后大于n，则会退出循环，设循环次数为x，n = 2^x，得到x = logn，所以这个算法的时间复杂度为O(logn)。

• 再举个平方阶的🌰

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];
           }
      }
 }

• 最后一个🌰

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

根据注释可得到，该算法执行的总次数为：1+(n+1)+n=2n+2，根据大O记法推导：
第一步用常数1取代运行时间中的所有加法常数，得到2n+1;
第二步保留最高阶项，得到2n;
第三步如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到该算法的时间复杂度为O(n)。