iOS算法基础之算法复杂度解疑

对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。一个算法的优劣往往通过算法复杂度来衡量，算法复杂度包括时间复杂度和空间复杂度。时间复杂度是算法的所需要消耗的时间，时间越短，算法越好。可以对算法的代码进行估计，而得到算法的时间复杂度。一般来说，算法代码简短精悍可以用来减少算法的时间复杂度！

空间复杂度指的是算法程序在执行时所需要的存储空间。空间复杂度可以分为以下两个方面！

1.程序的保存所需要的存储空间资源。即程序的大小；

2.程序在执行过程中所需要消耗的存储空间资源，如中间变量等；

一般来说，程序的大小越小，执行过程中消耗的资源越少，这个程序就越好！

算法复杂度统计方法

一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。事后统计的方法和事前分析估算的方法。事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。在编写程序前，依据统计方法对算法进行估算。

时间复杂度

时间频度是一个算法执行所耗费的时间，一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”。记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个O(n²)算法在n较小的情况下可能比 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

大O表示只是说有上界，由定义知如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)。另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n²+3n+4与T(n)=4n²+2n+1它们的频度不同，但时间复杂度相同，都为O(n²)。

按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log₂n),线性阶O(n), 线性对数阶O(nlog₂n),平方阶O(n²)，立方阶O(n³),...，k次方阶O(n^k),指数阶O(2ⁿ)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

常见的算法时间复杂度由小到大依次为：Ο(1)＜O(log₂n)＜Ο(n)＜O(nlog₂n)＜O(n²)＜O(n³)＜…＜O(2ⁿ)＜Ο(n!)

时间复杂度的计算

（1）找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

（2） 计算基本语句的执行次数的数量级；只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

（3）用大Ο记号表示算法的时间性能。将基本语句执行次数的数量级放入大Ο记号中。如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。

（4）对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间。对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"。对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间。对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"。乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1T2=O(f(n)g(n))。

对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度。另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数。

for (i=1; i<=n; i++)  
   x++;  
for (i=1; i<=n; i++)  
　for (j=1; j<=n; j++)  
      x++; 

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n²)，则整个算法的时间复杂度为Ο(n+n²)=Ο(n²)。

常见的时间复杂度说明

1、O(1)

    Temp=i; i=j; j=temp;                    

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

2、O(n²)

sum=0；                       (1)
for(i=1;i<=n;i++)            (n+1)
  for(j=1;j<=n;j++)          (n^2)
    sum++；                  (n^2)

解：因为Θ(2n²+n+1)=n²（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)=O(n²)；

for (i=1;i<n;i++)  
 {   
   y=y+1;         ①     
   for (j=0;j<=(2*n);j++)      
      x++;         ②        
 }  

解： 语句1的频度是n-1，语句2的频度是(n-1)*(2n+1)=2n²-n-1。f(n)=2n²-n-1+(n-1)=2n²-2；又Θ(2n²-2)=n²，该程序的时间复杂度T(n)=O(n²)。

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

3、O(n)

a=0;  
b=1;                      ①  
for (i=1;i<=n;i++)        ②  
{    
 s=a+b;　　　　③  
 b=a;　　　　　④    
 a=s;　　　　　⑤  
} 

解： 语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

4、O(log2n)

i=1;       ①  
while (i<=n)  
  i=i*2;   ② 

解： 语句1的频度是1,
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log₂n
取最大值f(n)=log₂n,
T(n)=O(log₂n )

5、O(n³)

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

解：3层循环，由上可知复杂度为O(n³).

常用的算法的时间复杂度和空间复杂度

同一个算法处理不同的输入数据所消耗的资源也可能不同，所以分析一个算法的复杂度时，主要有三种情况可以考虑，最差情况(Worst Case)下的，平均情况(Average Case)的， 最好情况(Best Case)下的。我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是O(n)，这是最坏的一种情况了。最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。平均情况更能反映大多数情况下算法的表现。平均情况分析就是对所有输入尺寸为n的输入，让算法运转一遍，然后取它们的平均值。当然，实际中不可能将所有可能的输入都运行一遍，因此平均情况通常指的是一种数学期望值，而计算数学期望值则需要对输入的分布情况进行假设，一般都是通过运行一定数量的实验数据后估算出来的。

考虑最好情况的复杂度更是没有意义。几乎所有的算法你都可以稍微修改一下，以获得很好的最好情况下的复杂度(要看输入数据的结构，可以是O(1)。怎样修改呢? 预先计算好某一输入的答案，在算法的开始部分判断输入，如果符合，给出答案。