算法分析神器—时间复杂度

你说一下这段代码会运行多长时间

这个...，得在计算机上跑一下才可以知道吧

恩恩，对的，那如果我改变n的大小为10000，你能够预测它的运行时间吗？

这个...,要不再测一次

我们要善于发现事物的内在规律

这个程序的内在规律是什么呢？

你要预测当n=10000的时候，这个程序会运行多长时间，你首先要知道程序的运行时间都花在哪了？

当电脑运行这段代码的时候，执行任何一条语句都需要花费时间，这是时间花费的主要地方

为了方便讨论，这里我们把每一条语句的执行时间都看做是一样的，记为一个时间单元

你看一下刚才的程序都有哪些语句

你看，这个程序有这么几个地方消耗了时间

那么一共花费了3n+3个时间单元,可以看出，程序消耗的时间和你的n成线性关系

现在我用T(n)表示这个程序运行了多长时间，那么这个程序运行的时间就可以写成T(n)=3n+3

其中的n被我们称为问题的规模，其实就是你处理问题的大小

本文主要讨论问题规模和运行时间的关系，假定不同输入和运行时间基本无关

哦，我懂了，要预测程序的时间，我可以把运行时间函数求出来

恩恩，对的

这个函数表达式看起来挺复杂的

我们常常会对这个函数进行简化，使得它既简单又不失函数的主要特性

哦？怎么简化

我们一般只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项，也就是最高次项

所以一般我们会保留最高次项并忽略该项的系数

这个忽略低阶项是什么意思

所谓低阶项，简单地说就是当n非常大时，这个项相对于另外一个项很小，可以忽略，比如n相对于n^2,n就是低阶项

哦，我怎么判断哪个是高阶，哪个是低阶呢？

具体要用数学知识，对你而言，你只需记住下面的大小关系就行了，到时按照这个进行忽略（相对较小的忽略）

简化完了之后呢？

化简完后的函数可以近似地代表原来函数的总体趋势

简化后的式子被称为这个程序算法的时间复杂度，记做O(f(n)),f(n)就是简化后的式子，比如说刚开始讨论的T(n)=3n+3,简化后T(n)~f(n)=n,那我们记为O(n)

更准确地说O代表了运行时间函数的一个渐进上界，即T(n)在数量级上小于等于f(n)

哦，原来时间复杂度可以表示某个算法的运行时间的趋势，大致地度量算法效率的好坏， 那我该如何算这个时间复杂度呢？

从前面可以总结出计算算法复杂度大O的方法

举个例子吧，先来看这样一段代码

显然，T(n)=3,对这个函数进行简化，用常数1取代常数3，然后取代后的函数没有最高阶项，那么这个算法的时间复杂度就是O(1).

O(1)也被称为常数阶

每次都要把时间函数算出来，好复杂，有没有简便一点的方法

这个还真可以耍耍小聪明，一般来说，最内层执行次数最多的语句就决定了整个算法的趋势

你只要看看最内层的语句执行次数的规律就行了，这个内层打印语句随着问题规模n的增加会呈线性增加，直接就可以判定复杂度为O(n)

这个方法真棒，那么按照这个方法就很容易得出下面这个嵌套的两层for循环的复杂度为O（n^2）了

恩恩，对的，最内层的语句随n的增加会呈二次函数的规律执行，代表了这个算法执行时间的一个趋势

我听说有一个很神奇的函数叫对数函数，它随着自变量的增大，因变量增长的很慢，这个应该很受欢迎吧

嗯嗯，对的，对数函数的趋势显然比线性函数好(对数函数随着自变量的增大因变量增长的很慢)

你看，这段代码的复杂度就为对数级别的，O(logn)

这个怎么分析

和之前的分析方法一样，我们着重看执行次数最多的内层代码语句

每循环一次，sum就给自身乘以2，乘了多少次就跳出循环了呢(大于等于n)？不知道，就设为x吧，那么2^x=n,解出x=logn，这说明随着n的增大，最消耗时间的内层语句是呈对数变化的

哦，我懂了，原来如此

复杂度的内容很多，你只要理解它的含义以及会分析简单的算法就行了，以后遇到复杂的，为师会给你传授的

好的