分析算法

说在开始

在本文中，我们将探讨下所谓的算法复杂到底是个什么玩意，以及各种奇奇怪怪的表示符号。

分析insertion sort算法

让我们从我们最早接触的插入算法开始，这里，我们不纠结于其具体的代码实现形式，只考虑其核心步骤，毕竟具体的代码实现都是大同小异的。现在我们回过来看我们的插入算法。我们把代码精简一下，变成伪代码。其实一般编写算法也是先写出伪代码然后在进行分析和具体实现的，当然我觉得直接上实例代码也应该是大差不差的，只不过少了一些细节部分罢了。这里希望你还记得插入算法是如何实现的，如果有些记不住了，建议翻一翻前面的文章。

A=[1,2...,n]
for j from 2 to n:
    key = A[j]
    i = j-1
    while i>0 and A[i]>key:
        A[i+1] = A[i]
        i -= 1
    A[i+1] = key

如上即为插叙算法的伪代码，接下来我们来试着分析一下，首先我们假设电脑执行每一行的代码所需要的时间都为a，接下来我们看看每行代码执行的次数，第一行很明显只在开始执行一次，时间即为a*1,接下来看第二行，从2到n需要执行(n-1)次才能全部遍历完数组，第三第四行也是如此，来到第五行，对于每次j，i都要遍历其左边的所有数，所以所执行的时间应该是a*(n-2)，对于每次for循环都执行遍while循环，所以总的时间应该是a*(n-2)*(n-1)，于六，七行也是如此，最后一行很明显也是a*(n-1)。接下来我们看看这段伪代码所需的总的时间，应该是T(n)=a+a*(n-1)*4+a*(n-2)*(n-1)*3。展开化简一下T(n)=3a*n² -5a*n+3a。

需要注意的，这里我们使用T(n)来表示代码对于n个输入执行所需的时间函数，你可以简单理解为f(x)，本质上是一样的，n就像x一样为自变量。还需要注意的是，这里我考虑的是最坏的情况，也就是当数组里的数是从大到小排序时进行重新排序所需要的时间，一般我们进行分析也是考虑最坏的情况，下文我还会在进行阐述。

渐进符号

接来下我们来认识一下用于表达算法运行所需时间的一些符号，其中就有经常见到的O，当然不止大O，接下来我们一一阐述。

Θ符号

如上文我们见到的T(n)=3a*n² -5a*n+3a，我们可以使用Θ(n²)表示,直接忽略掉它的低阶项和前面的系数，这是因为我们计算机所设计的算法一般都是用于处理成百上千W的数据，所以在庞大的底数基础上，函数的增长率就十分的重要了，而低项集和系数对于函数的增长率的影响其实是微乎其微的(这里其实应该放些函数图像的图片的，但我偷个懒，你们用自己的大脑计算器跑一跑函数图像然后宏观观察一下)。接下来看看其定义。

数学定义就是如此，看起来云里雾里的，不过别担心，我来试解释一番，首先我们得明确，这里得g(n)和f(n)都是两个关于n的函数，而且他们不是同一个函数，这在高数中也非常常见，是不是有些后悔没好好学高数了？我也后悔了（手动滑稽），但不必担心，我们需要运用高数的地方其实并不多。这里的g(n)就等于上文的n² ,而f(n)我们可以理解为是上文的T(n),注意是只保留了高项集和其系数的T(n),(事实上是带后面的低项集的，但其影响就和我上文所说的一样，影响微乎其微，所以就可以不在意这么多细枝末节了)，所以f(n)就应该是3a*n² ，那么接下来就简单明了了，我存在两个常数，可以使得定义中的最后一句话成立（才不是懒得打字呢）。那么是什么意思呢？我们可以大胆假设一下这两个常数是2a和4a，那么两个函数就会是2a*n² 和4a*n² 然后对于一个界限n₀ ，在这个界限之后最后那个等式恒成立，这里我把书上的图贴上来会比较好理解点。

这里我们称g(n)是f(n)的一个渐近紧确界，（又是个奇奇怪怪的名词，感觉所有的课程就是奇奇怪怪的名词学习），我们主要注意其具体功能就好，即g(n)所表达的意思，在这里g(n)既可以表示上界，也可以表示下界，上界下界可以简单理解为运行时间所需的最大时间和最小时间，或是最差状态和最优状态。

O符号

终于等到你~还好我没放弃~
终于啊，终于看到了这个游荡在互联网上的符号，天天只闻其名不知其意的日子到头了。但在这里我并不会进行过多的阐述，毕竟他的意义就是用来表示运行的最大时间，最差状态，如果你掌握了Θ符号，这个O符号表示的就是只要他的上半部分，只考虑上界。（虽然只是困惑不知道怎么算吧，但经过了开头的小教学，你应该是有了一定的理解如何计算了）。这里我把定义和图像贴出，简单带过一下。