算法分析专题：时间复杂度

本文主要是介绍算法分析专题：时间复杂度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

        时间复杂度是我在刚刚踏入计算机专业时遇到的第一个难题。初学C语言的时候，并未接触到这个概念，写代码纯靠自己发挥，对时间复杂度空间复杂度从未有所考量。结果进入大二就悲剧啦，当待处理数据量上升到百万甚至一亿的规模上，往往花了好久写出来的代码却不能满足题目的时间要求，而唯一的解决办法就是把可能是一天的工作换一种思路重新再写一遍，程序超时的痛苦真的无以言表。而时间复杂度分析就是避免程序超时的最有效方法，对于准备学习计算机专业的同学来说，掌握算法的时间复杂度分析至关重要！

        算法分析包括时间复杂度分析和空间复杂度分析。事实上，空间复杂度分析并没有时间复杂度分析重要，这一点我们后面会讲解。如果我们把生活中解决问题的过程抽象为程序代码的设计，那么时间复杂度就可以抽象为我们解决问题所花费的时间。于是有请本文嘉宾小蓝登场：

        小蓝发现今天自己的日程还有三项：一、去北湖跑步，二、去食堂吃饭，三、回宿舍洗澡。小蓝不能同时去做这三项任务中的任意两项，所以他要决定这三项任务的先后顺序。小蓝发现，洗澡不能在跑步之前，因为这样小蓝就需要在跑步后再洗一次澡；此外，吃饭不能在跑步之前，因为吃完饭立刻跑步很容易胃下垂，并且小蓝没有等待晚饭消化的时间。小蓝并不想做重复无用和没必要的工作，所以小蓝决定立刻去跑步，然后去洗澡，最后去吃饭，以至于它可以不间断地利用最短时间完成这三项日程。

        实际上，这就是小蓝解决问题的途径，也就是算法。每一种算法都对应着一种时间复杂度，可以抽象为小蓝完成任务所要花费的时间。生活中我们所解决的不少问题都透露着最优解决的思想，也就对应着最优的时间复杂度。小蓝可以完成这三项日程的顺序有多种，每一种方法都可以进行时间复杂度分析，从而估算出实现该算法大致所需要的时间。时间复杂度的作用就是这样，我们来看关于时间复杂度的定义：

        “计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。”

        即算法的时间复杂度是输入数据规模的函数，若输入待处理数据量为n，则时间复杂度记为O(n)。时间复杂度可以简单理解为处理规模为n的问题算法需要运算的次数，是对算法运行次数的限界。常用的标准时间复杂度函数及他们之间的关系如下所示：

        其中，黑色部分为多项式时间阶，表示算法以多项式时间为限界。红色部分成为指数时间阶，表示算法以指数时间为限界。我们所定义的有效算法，即是以多项式时间为限界的算法。上述标准时间复杂度函数的关系有以下三个特点，再看下面的例子之前，需要体会这三个特点，以便更好地理解。

        （1）上式不等号不可以划等号

        （2）log无特殊说明是以2为底的对数函数

        （3）上式在n较大的情况下才成立

        接下来我们来看几个算法时间复杂度分析的例子，以下代码段皆为某算法的关键代码。

例一：  

int function(int n)

{

    int i=n;//执行一步操作，运行次数为1

    int j=n+1;//执行一步操作，运行次数为1

    return i+j;

}

        可见该函数运行的时间复杂度以一个常数为限界，时间复杂度为O(1)。

例二：

int function(int n)

{

    int i=1;//执行一步操作，运行次数为1

    while(i<=n)//执行logn步操作，运行次数为logn

    {

        i=i*2;

    }

    return i;

}

        由于O(logn)>O(1)，所以该函数整体时间复杂度为O(logn)。

例三：

int function(int n)

{

    int i=1;

    while(i<=n)//执行n步操作，运行次数为n

    {

        i++;

    }

    return i;

}

        由于循环体执行次数为n，故该函数整体时间复杂度为O(n)。

例四：

 int function(int n,int m)

{

int sum=0;

for(int i=0;i<m;i++)//执行m步操作，运行次数为m

{

    for(int j=0;j<n;j++)//执行logn步操作，运行次数为logn

        {

        sum+=i*j;

            j*=2;

        }

    }

    return sum;

}

        由于外循环体运行次数为m，内循环体运行次数为logn，故函数整体时间复杂度为O(mlogn)。

例五：

int function(int n)

{

    int sum=0;

    for(int i=0;i<n;i++)//执行n步操作，运行次数为n

    {

        for(int j=0;j<n;j++)//执行n步操作，运行次数为n

        {

            sum+=i*j;

        }

    }

    return sum;

}

        由于外循环体运行次数为n，内循环体运行次数为n，故函数整体时间复杂度为O()。

例六：

int function(int n,int m)

{

    int sum=0;

    for(int i=0;i<m;i++)//执行m步操作，运行次数为m

    {

    for(int j=0;j<n;j++)//执行logn步操作，运行次数为logn

        {

            sum+=i*j;

            j*=2;

        }

    }

    for(int i=0;i<n;i++)//执行n步操作，运行次数为n

    {

    for(int j=0;j<n;j++)//执行n步操作，运行次数为n

        {

            sum+=i*j;

        }

    }

    return sum;

}

        第一次循环的时间复杂度函数为O(mlogn)，第二次循环的时间复杂度函数为O()，由于O()>O(mlogn)，即O()作为用于表述算法的时间复杂度函数更为精确，函数整体时间复杂度为O()。

        以上就是对算法的时间复杂度最基本的分析，熟悉以上方法后可以对以后所学习的算法学以致用。求出算法的时间复杂度后，我们知道，时间复杂度是算法运行次数的一个表征。当我们知道计算机每秒所能执行操作的次数后，我们就可以根据输入数据的规模对算法的实际运行时间做出大致的考量，这就是时间复杂度最为常见的用途。

        而通常情况下，竞赛环境中要求运行时间为1秒。计算机一秒可以执行操作的次数为10亿次。我们可以发现，使用时间复杂度为O(logn)的算法，一秒钟可以解决输入数据规模为2的10亿次方的问题；使用时间复杂度为O(n)的算法，一秒钟可以解决输入数据规模为十亿的问题；使用时间复杂度为O()的算法，即以多项式时间为限界的算法，一秒钟可以解决输入规模为的问题；而当算法时间复杂度达到指数时间阶时，如O()，此时一秒钟只能解决输入数据规模小于等于29的问题，同样问题运行时间则远远超过以多项式时间为限界的算法，因此，我们很少使用时间复杂度为指数时间阶的算法来解决问题。

        空间复杂度则是对算法的另一方面的考量，即使用空间的大小，通常表现在变量或者数组的数量。前面我们提到，对于算法空间复杂度分析往往不是我们的重点，因为在实际编写代码的过程中，我们常常通过牺牲空间的方式来换取时间，即我们不在乎空间复杂度，并且通过提升算法使用空间大小来提高算法的时间复杂度，以实现算法更高的效率。小蓝说的，时间就是金钱！

        算法分析的必要性在于，当我们设计算法的思路时，需要对算法运行次数进行考量，当我们使用指数时间阶的算法解决问题时，输入规模仅仅为100，但却可能要计算上几十万年，而这是不可能适用于解决问题的。并且，算法在不断发展的过程中，也伴随着解决问题的最优方法的发展，人们追求者更快更优的算法，并且新算法的产生往往能使得计算机领域产生新的发展，甚至伟大的变革。着眼当下，在算法竞赛中不仅仅要求答案的正确，优秀时间复杂度的算法才能拿到题目的最高分；找工作时，面试官往往也会对你研究算法的能力就行考量，考量的标准呢？可不就是算法的最优性嘛！

        以上内容就是对算法分析的初步介绍，包括时间复杂度分析与空间复杂度分析。标准时间复杂度函数表示算法的计算时间以该函数为限界，是考量算法最优性的重要指标。空间复杂度分析往往并不重要，通常我们采用牺牲空间的方式来提升算法的时间复杂度，感兴趣的同学可以查阅相关资料加深理解。小蓝温馨提示：算法分析是正式开始学习算法的第一步，也是必须要打好的基础，一定要内化为一种自然而然的思想，一定会对今后算法学习大有裨益。

        本文结束，感谢支持！

这篇关于算法分析专题：时间复杂度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！