数据结构第二篇 算法的符号大O

为什么要学习算法呢

知道一个算法执行多快占用多少空间非常有用，以此来选择解决当前问题的算法。
大 O 符号让你能粗略的估计算法的运行时间和他使用了多少内存。
一个最坏的例子算法的运行需要的时间是O(n ^ 2)，并且使用O(n)的空间。那么这个算法真的运行缓慢还需要很多额外的空间。
计算大O的算法通常是通过数据分析进行的。我们跳过数学分析，这个n关联的是需要处理数据的数量，例如你对一个100个元素的数组排序那么 n = 100。

在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度。

这里对数学忘了的童鞋我们来复习下数学的对数和指数等方面的知识以便于我们来理解这几个函数公式代表的意思。

对数百度百科解释：如果a的x次方等于N（a>0，且a不等于1），那么数x叫做以a为底N的对数（logarithm），记作x=logaN。其中，a叫做对数的底数，N叫做真数。
举个例子：
以2为底8的对数就是3。套入上面的概念，2（a）的3（x）次方等于8（N）,那么数3叫做以2为底8的对数，记作3 = log2 （8） 。由于把8放到右上角很难打出来所以这里省略为3 = log2 （8）也记做 log（8）。
注意：在大 O 记法中 log （n）的底数有可能是其他常数 比如2，3。如果是10，可以写作 lg （n）。

指数百度百科解释：指数是幂运算aⁿ(a≠0)中的一个参数，a为底数，n为指数，指数位于底数的右上角，幂运算表示指数个底数相乘。当n是一个正整数，aⁿ表示n个a连乘。当n=0时，aⁿ=1。
我们来理解下 ：幂运算 8=2x2x2 2的三次方标识3个2连乘 。对数运算 3 = log 2 （8）。
他们之间什么关系呢看图：

对数和指数的关系图

下面我们来举几个例子解释下上面几个常见的复杂度函数公式

O(1) 常熟阶 这个是最好的，不管你处理多少数据，该算法执行的时间是一样的。比如从取数组里面第一个下标的元素。

NSArray *testArray = @[@"2",@"5”];
  NSString *testStr = testArray[1];

当然之前我们讲的进栈出栈也是这个复杂度。
这个算法的运行次数f(n) = 1,根据推导大O阶的方法，第一步是将1改为1，在保留最高阶项是，它没有最高阶项，因此这个算法的时间复杂度为O(1);
注意：不管这个常数是多少，3或12，都不能写成O(3)、O(12)，而都要写成O(1)。

O(logn) 对数阶 当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。举个简单的例子

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

可能大家看这个有点模糊解释下：
语句1的频度是1, 设语句2的频度是f(n),
则：2^f(n)<=n;f(n)<=log2n ， 取最大值f(n)=log2n, T(n)=O(log2n ) 可能这个看着有点不是像高中学习的格式，我手写了下看下图：

手书

O(n) 线性阶 性能良好，代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法，顺序搜索。举个例子

    NSArray *testArray = @[@"2",@"5"];
    
    for (NSInteger i = 0; i < testArray.count; i++)
    {
        NSLog(@"%@",testArray[i]);
    }

这个算法的运行次数f(n) = n, 也就是O(n) 因为循环体中的代码须要执行n次。

O(n log n) 线性对数阶 和上面概念类似 就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。举个例子

 for (i = 0; i< n ; i ++)
    {
        int j = 1;
        while (j <= n)
        {
            j *= 2;
        }
    }

解释：和上面对数阶多了一层循环 就是乘以n

O(n^2) 平方阶 代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。举个例子

for (int i = 0; i < n ; i++)
    {
        for (int j = i ; j < n; j++)
        {
            
        }
    }

注意：上面的内层循环j = i ;而不是0
因为i = 0时，内层循环执行了n次，当i=1时，执行了n-1次……当i=n-1时，执行了1次，所以总的执行次数为：
n+(n-1)+(n-1)+...+1 = n(n+1)/2 = n2/2 + n/2
根据大O推导方法，保留最高阶项，n2/2 ，然后去掉这个项相乘的常数，1/2
因此，这段代码的时间复杂度为O(n2)

O(n^3) 立方阶 这个性能比较差 也就是说表数据量增大n倍时，耗时增大n的立方倍

for(i=0;i<n;i++)  
   {    
      for(j=0;j<i;j++)    
      {  
         for(k=0;k<j;k++)  
            x=x+2;    
      }  
   }  

解释：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).

总结：

通常你不需要推算，可以大概估算下。如果一层循环是O (n) ，如果是两层循环就是 O(n^2) 三层循环就是 O(n^3)，以此类推。
这个大O也是估计，和这个n 有很大的关系。例如,最坏的情况下(插入排序)算法的O(n ^ 2),在理论上,比运行时间(归并排序)算法的*O(n log n)要差。但对于少量的数据,插入排序是更快。