数据结构与算法——3.时间复杂度分析1（概述）

前面我们已经介绍了，研究算法的最终目的是如何花费更少的时间，如何占用更少的内存去完成相同的需求，并且也通过案例演示了不同算法之间时间耗费和空间耗费上的差异，但我们并不能将时间占用和空间占用量化。因此，接下来我们要学习有关算法时间耗费和算法空间耗费的描述与分析。有关算法时间耗费分析，我们称之为算法的时间复杂度分析。

1.时间复杂度分析方法

我们要计算算法耗费时间情况，首先我们得度量算法的执行时间，那么如何度量呢？

1.1事后分析估算方法

比较容易想到的方法就是我们把算法执行若干次，然后拿个计时器在旁边计时，这种事后统计的方法看上去的确不错，并且也并非要我们真的拿个计算器在旁边计算，因为计算机都提供了计时的功能。这种统计方法主要是通过设计好的测试程序和测试数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低，但是这种方法有很大的缺陷︰必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境(硬件环境)的差别导致测试的结果差异也很大。

 如下例所示：

 public static void main(String[] args) {long start = System.currentTimeMillis();int sum = 0;int n = 100;for (int i = 1; i <= n; i++) {sum +=i;}System.out.println("sum="+sum);long end = System.currentTimeMillis();System.out.println(end-start);}

如何理解该方法的缺陷？
举例说明：比如我们用来三天的时间写了一个测试某个确定算法的程序，然后运行它，测试这个算法的时间，发现测试时间很长，那在实际中这个算法肯定就不能使用啊，那也就是说这个算法是不好的，是有缺陷不能用的，那么你写的这个测试程序也是不能用的，也就是说你白花了三天时间。这就是一个极大的缺陷。

1.2事前分析估算方法

在计算机程序编写之前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序，程序在计算机上运行消耗的时间取决于下列因素：

1. 算法采用的策略和方案；
2. 编译产生的代码质量；（不可人为干预）
3. 问题的输入规模（所谓的问题输入规模就是输入量是多少）；
4. 机器执行指令的速度；（不可人为干预）

由此可见，抛开那些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。

2.案例说明

2.1案例一

题目：计算1到100的和

方法一：

//如果输入量n为1，则需要计算1次//如果输入量n为1亿，则需要计算1亿次
public static void main(String[] args) {int sum = 0;  //执行1次int n = 100;  //执行1次for (int i = 1; i <= n; i++) {//执行n+1次sum +=i;  //执行n次}System.out.println("sum="+sum);}

方法二：

    //如果输入量n为1，则需要计算1次//如果输入量n为1亿，则需要计算1亿次public static void main(String[] args) {int sum = 0;  //执行1次int n = 100;  //执行1次sum = (n+1)*n/2; //执行1次System.out.println("sum="+sum);}

分析：

方法一，当输入规模为n时，方法一执行了1+1+（n+1）+n=2n+3次

方法二，当输入规模为n时，方法二执行了1+1+1=3次

定量具体分析来看，很明显，方法二的执行次数是要远少于方法一的。

下面，我们来深入分析一次这两段代码：

方法一，这个算法求和的核心代码是那个for循环，如果我们把这个for循环看成是一个整体，不考虑什么判断条件啊，什么次数啊，只考虑这个循环里面的内容，然后再忽略其他的一些简要的一次就执行的代码，那么方法一的执行次数就简化为n次

方法二，同样的道理，我们简化那么简单的一次就行的代码语句，重点关注算法的核心语句的执行次数，那么方法二的执行次数就简化为1次

再对比一下，两个方法运行时间的差距就是n与1的差距。

注意：这里我们用了简化思维，直接去抓取每个算法的核心部分，并分析这个核心部分执行的次数

问题：

为什么循环判断条件在方法一中执行了n+1次，看起来是个不小的数字，但是可以忽略呢？

答：看2.2案例二

2.2案例二

题目：计算100个1+100个2+100个3+,,,,,,+100个100的结果

public static void main(String[] args) {int sum = 0;int n = 100;for (int i = 1; i <= n; i++) {for (int j = 1; j <=n ; j++) {sum+=i;}}System.out.println("sum="+sum);}

上面这个例子中，如果我们要精确的研究循环的条件执行了多少次，是一件很麻烦的事情，并且，由于真正计算和的代码是内循环的循环体，所以，在研究算法的效率时，我们只考虑核心代码的执行次数，这样可以简化分析。

下面给出2.1中问题的四个答案，可以酌情选择思考

答案1：精确循环次数很麻烦

第一个for循环的条件判断执行了100次，第二个for循环的条件判断执行了10000次，但是请思考下面的几种情况：如果有5层循环，每层次数不一样，让你求第4层循环的判断次数，是不是很麻烦？如果上题中，n=1234，求第二层循环的判断次数是不是也很麻烦？所以，我们忽略循环的判断次数。

答案2：只关心得到结果的最核心部分

上面的所有循环都是为了sum+=i 这句服务的，并且这个算法的最核心部分也是sum+=i，最后的结果也是由这一句得到的，所以，我们只关心这一句。

答案3：当做整体看

因为你每执行一次sum+=i 这句，那就比如执行了前面的for循环的条件判断啊，这二者是一个整体的，是密不可分的，所以就忽略了for的条件判断，只关心那一句

答案4：老师讲的！

我们研究算法复杂度，侧重的是当输入规模不断增大时，算法的增长量的一个抽象(规律)，而不是精确地定位需要执行多少次，因为如果是这样的话，我们又得考虑回编译期优化等问题，容易主次跌倒。
我们不关心编写程序所用的语言是什么，也不关心这些程序将跑在什么样的计算机上，我们只关心它所实现的算法。这样，不计那些循环索引的递增和循环终止的条件、变量声明、打印结果等操作，最终在分析程序的运行时间时，最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行时间，最重要的就是把核心操作的次数和输入规模关联起来。

3.函数渐进增长

概念：

给定两个函数f(n)和g(n)如果存在一个整数N，使得对于所有的n>N,f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于(gn)。概念似乎有点艰涩难懂，那接下来我们做几个测试。

3.1测试1

假设四个算法的输入规模都是n ：

1. 算法A1要做2n+3次操作，可以这么理解︰先执行n次循环，执行完毕后，再有一个n次循环，最后有3次运算
2. 算法A2要做2n次操作
3. 算法B1要做3n+1次操作，可以这个理解∶先执行n次循环，再执行一个n次循环，再执行一个n次循环，最后有1次运算
4. 算法B2要做3n次操作

那么，上述算法，哪一个更快一些呢?

通过数据表格，比较算法A1和算法B1 ∶

• 当输入规模n=1时，A1需要执行5次，B1需要执行4次，所以A1的效率比B1的效率低；
• 当输入规模n=2时，A1需要执行7次，B1需要执行7次，所以A1的效率和B1的效率一样；
• 当输入规模n>2时，A1需要的执行次数一直比B1需要执行的次数少，所以A1的效率比B1的效率高

所以我们可以得出结论︰

                当输入规模n>2时，算法A1的渐近增长小于算法B1的渐近增长

通过观察折线图，我们发现，随着输入规模的增大，算法A1和算法A2逐渐重叠到一块，算法B1和

算法B2逐渐重叠到一块，所以我们得出结论︰

                随着输入规模的增大，算法的常数操作可以忽略不计

3.2测试2

假设四个算法的输入规模都是n :

1. 算法C1需要做4n+8次操作
2. 算法C2需要做n次操作
3. 算法D1需要做2n^2次操作
4. 算法D2需要做n^2次操作

那么上述算法，哪个更快一些?

 

通过数据表格，对比算法C1和算法D1 :

• 当输入规模n<=3时，算法C1执行次数多于算法D1，因此算法C1效率低一些；
• 当输入规模n>3时，算法C1执行次数少于算法D1，因此，算法D2效率低一些，所以，总体上，算法C1要优于算法D1

通过折线图，对比对比算法C1和C2：

        随着输入规模的增大，算法C1和算法C2几乎重叠

通过折线图，对比算法C系列和算法D系列：

        随着输入规模的增大，即使去除n^2前面的常数因子，D系列的次数要远远高于C系列。

因此，可以得出结论：

        随着输入规模的增大，与最高次项相乘的常数可以忽略
 

3.3测试3

假设四个算法的输入规模都是n：

• 算法E1：2n^2+3n+1；
• 算法E2：n^2
• 算法F1：2n^3+3n+1
• 算法F2：n^3

那么上述算法，哪个更快一些?

通过数据表格，对比算法E1和算法F1 :

• 当n=1时，算法E1和算法F1的执行次数一样；
• 当n>1时，算法E1的执行次数远远小于算法F1的执行次数；

        所以算法E1总体上是由于算法F1的。

通过折线图我们会看到，算法F系列随着n的增长会变得特块，算法E系列随着n的增长相比较算法F

来说，变得比较慢，所以可以得出结论：

        最高次项的指数大的，随着n的增长，结果也会变得增长特别快

3.4测试4

假设五个算法的输入规模都是n ：

• 算法G ：n^3；
• 算法H：n^2；
• 算法I：n；
• 算法J：logn；
• 算法K：1；

那么上述算法，哪个效率更高呢?

通过观察数据表格和折线图，很容易可以得出结论：

        算法函数中n最高次幂越小，算法效率越高

3.5小结

总上所述，在我们比较算法随着输入规模的增长量时，可以有以下规则：

1. 算法函数中的常数可以忽略
2. 算法函数中最高次幂的常数因子可以忽略
3. 算法函数中是高次幂越小，算法效率越高

4.大O计法

4.1具体定义

定义：

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情

况并确定T(n)的量级。算法的时间复杂度，就是算法的时间量度，记作：T(n)=O(f(n))。它表示随

着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简

称时间复杂度，其中f(n)是问题规模n的某个函数。

        在这里，我们需要明确一个事情：执行次数=执行时间

        用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n

的增大，T(n)增长最慢的算法为最优算法。

4.2案例分析

下面用大O表示法来表示一些求和算法的时间复杂度

算法一：

    public static void main(String[] args) {int sum = 0;//执行1次int n = 100;//执行1次sum = (n+1)*n/2;//执行1次System.out.println("sum="+sum);}

算法二：

    public static void main(String[] args) {int sum = 0;//执行1次int n = 100;//执行1次for (int i = 1; i <= n; i++) {sum+=i;//执行n次}System.out.println("sum="+sum);}

算法三：

 public static void main(String[] args) {int sum = 0;//执行1次int n = 100;//执行1次for (int i = 1; i <= n; i++) {for (int j = 1; j <=n ; j++) {sum+=i;//执行n^2次}}System.out.println("sum="+sum);}

如果忽略判断条件的执行次数和输出语句的执行次数，那么当输入规模为n时，以上算法执行的次

数分别为：

算法一：3次

算法二：n+3次

算法三：n^2+2次

如果用大o记法表示上述每个算法的时间复杂度，应该如何表示呢？基于我们对函数渐近增长的分

析，推导大O阶的表示法有以下几个规则可以使用：

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数中，只保留高阶项
3. 如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数

所以，上述算法的大O计法分别为：

        算法一：O(1)

        算法二：O(n)

        算法三：O(n^2)

5.小结

这篇文章，首先我们给出了算法的时间复杂度的分析方法，引导我们如何去分析一个算法的时间复杂度，然后讲了一系列的函数渐进增长，通过具体的实例总结了一些结论，最后我们在这些结论的基础上提出来大O计法，然后结合大O计法和那些结论，我们实际的分析了一些求和算法的时间复杂度。