深入分析算法的复杂度

在系统分析算法的复杂度之前，我们先了解什么是算法？算法是指用来操作处理数据、解决程序问题的一组方法。但是对于同一个问题，我们去使用不同的算法，结果或许会一样，但不同的地方就在于你所用算法所耗费的资源和时间，这就是我们接下来学习算法的原因，不同的算法，产生的效率也不同，我们需要从中找出最合适的算法。

复杂度的分析

一. 时间维度

是指执行当前算法所消耗的时间，我们通常用时间复杂度来描述。

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

时间复杂度

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度。记作：T(n)=O(f(n))。它表示随着问题规模n的扩大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的函数。

一般情况下，随着输入规模n的增加，T(n)增长最慢的算法为最优算法。

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

如何分析一个算法的时间复杂度呢？

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

求解算法的时间复杂度的具体步骤

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

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

（3）用大Ο记号表示算法的时间性能。将基本语句执行次数的数量级放入大Ο记号中。

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

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

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

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。

（4）在计算算法时间复杂度时有以下几个简单的程序分析法则:

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)))

特别地，若T1(m)=O(f(m)), T2(n)=O(g(n))，则 T1(m)+T2(n)=O(f(m) + g(n))

3. 对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

4. 对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))

5. 对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

二、空间维度

类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用S(n)来定义。

空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，也是使用大O表示法。

（1）常量空间：存储空间大小固定，和输入没有关系时，空间复杂度是O(1)

（2）线性空间：算法中定义了一个线性集合，如一个列表，并且集合大小和输入规模n成正比，空间复杂度记为O(n)

（3）二维空间：算法中定义了一个二维列表集合，并且集合的长和宽都和输入规模n成正比，空间复杂度记为O(nn)/O（nm)

（4）递归空间：递归过程就是一个进栈和出栈的过程，当进入一个新函数时，进行入栈操作，把调用的函数和参数信息压入栈中；当函数返回时，执行出栈。递归的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

以上就是关于复杂度的内容，总的来说，衡量不同算法的优劣，主要还是根据算法所占的空间和时间两个维度去考虑。世界上没有绝对完美的事情，总会有很多缺憾，而我们要做的就是在其中找出最适合的解决方案。