时间复杂度与空间复杂度

在开始之前，先考虑一个问题 ： 给定义个算法，如何衡量这个算法的好坏？

通常，在给定义个算法，我们在确定这个算法是否正确以及算法的好坏时，需要做以下操作。第一就是首先要确定算法是正确的,通过数学上证明算法的正确性, 在其正确性的基础上，需要考虑算法的性能以及稳定性了。算法的性能一般包括两部分内容: 时间复杂度与空间复杂度。通过两者结合来评价算法的性能

一个算法是否为一个优秀的算法，是否为最优解？ 就需要有一个标准来衡量一个算法的好坏。 一个算法的好坏，需要从三个方面来衡量： 时间复杂度 、 空间复杂度、稳定性

时间复杂度

时间复杂度反应了程序执行时间随着输入规模增加而增长的量级，在很大程度上反应了当前算法的性能。算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。如何去度量一个算法的运行时间呢？

时间复杂度统计方式

1. 事后统计

事后统计的方式虽然可以在一定程度上反应算法的运行时间，不过此方式并不是优秀的解决方案，牵扯到的外部因素太多。通过此方式，必须先要将算法实现并运行； 时间统计依赖计算机硬件、软件环境等因素，以及算法的输入量等因素。所以并不能根本上反应算法运行时间，只能反应当前输入量下当前软硬件环境下的运行时间。有时候容易掩盖算法本身的优劣问题(有些算法会随着输入量的不同性能也会有很大不同)

2. 事前分析估算

事前分析是在编写算法之前，根据算法的数学可行性的数学分析分析，依据数学统计的方式对算法的性能做估算。一般一个算法的优劣将受以下因素影响：

1. 算法采用的方法
2. 编译产生的代码质量
3. 问题的输入规模
4. 机器执行指令的速度

因为有些因素是无法量化估量的，所以根据算法实现，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

通过以上方式了解了时间复杂度的计算过程中涉及到的因素以及时间复杂度的统计方式，那么到底如何统计时间复杂度呢？ 在具体的统计时间复杂度之前，还需要了解 时间频度概念

时间频度

要想获取一个算法的执行时间，通过数学统计的方式是无法获取的，必须要将算法进行运行才可以知道在当前软硬件环境下算法的具体执行时间。但在实际工作中，并不能对每个算法都进行实现并运行，往往只需要大致知道那个算法的花费多，那个算法的时间花费少就可以了，往往工作中只需要较优解(比较级中最优解)。分析得出一个算法的时间花费与代码语句的执行次数是成正比的。所以简单理解就可以抽象为计算代码语句的执行次数.此代码语句的执行次数就为时间频度T(n)

算法复杂度只关心针对算法影响最大的部分，在不同的算法中，算法语句执行次数为一个常数，则时间复杂度为 O(1), 因其只对影响最大的部分进行统计，所以在时间平度不同时，时间复杂度可能相同。 常见的时间复杂度：

常数阶     O(1) 
对数阶     O(log2^n) // log 2 的 n 次方 
线性阶     O(n) 
线性对数阶   O(nlog2^n) //  
平方阶     O(n^2)
立方阶     O(n^3) 
k次方阶    O(n^k)  
指数阶     O(2^n)

随着问题规模的变大，以上的时间复杂度也会变大，算法的执行性能变小

时间复杂度的比较 O(1)<O(log2^n)<O(n)<(nlog2^n)<O(n^2)O(n^3)...<O(2^n)< O(n!)

时间复杂度求解

1. 找出基本语句 算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体
2. 计算基本语句的执行此处的数量级
   只需要计算基本语句的执行次数数量级。即只要保证基本语句执行次数的函数中的最高次幂正确即可
3. 用O表示时间性能

如果算法中包含嵌套循环，基本语句通常是最内层的循环体，如果算法包含并列循环，则将并列循环的时间复杂度相加

分析时间复杂度

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

常见时间复杂度说明

1. O(1) temp=1;i=j;j=temp;
   以上三条语句执行与问题规模n无关。其算法复杂度为常数阶 T(n) = O(1).如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

2. O(n^2)

    sum=0；                 （一次）  
    for(i=1;i<=n;i++)     （n+1次）  
        for(j=1;j<=n;j++) （n2次）  
            sum++；            （n2次）
   

   以上代码时间复杂度为 (2n^2 +n + 1) -----> O(n^2)

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

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(log2^n)

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

   语句1的频度是1,

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

总结

简单总结，计算时间复杂度可以通过针对算法中循环体进行计算

空间复杂度

和时间复杂度相同，一个算法在运行中临时消耗的存储空间度量.算法在运行过程中，并不仅仅占用算法本身需要的参数数据空间。其部分算法会在运行过程中占用部分交换数据空间，这部分空间随着算法的不同而不同，有的甚至不需要交换数据空间。有的算法占用的临时空间与数据规模n 有关，其具体的衡量与时间复杂度相似

总结

一个算法的优劣，很大程度上取决于算法的时间复杂度，空间复杂度对算法的影响有限，在算法的衡量过程中，时间是最重要的因素，其次还有算法的稳定性，算法的稳定性也一定程度上取决于时间复杂度

参考

时间复杂度与空间复杂度 时间复杂度和空间复杂度

附录