目录

一、数据结构与算法关系

二、算法定义

三、算法的特性

四、算法设计的要求

五、算法效率的度量方法

六、函数的渐进增长

七、算法时间复杂度

1.定义

2.推导大O阶方法

3.常数阶

4.线性阶

5.对数阶

6.平方阶

 7.常见的时间复杂度

8.最坏情况与平均情况 

八、算法空间复杂度

九、总结

一、数据结构与算法关系

数据结构与算法的关系，就像祝英台离不开梁山伯，罗密欧离不开朱丽叶

两者结合，如双剑合璧，所向披靡

二、算法定义

什么是算法呢？算法是描述解决问题的方法

算法（Algorithm）这个词最早出现在波斯数学家阿勒·花剌子密在公元前825年（相当于我们唐朝时期）所写的《印度数学算术》中（说实话，他这名字我差点看成叫花子）

如今普遍认可的对算法的定义：

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

对于给定的问题，是可以有多种算法来解决的

大家就可能问，有没有通用的算法呀？一劳永逸呀

答案当然是没有，现实世界中问题千奇百怪，算法当然也就千变万化，没有通用的算法可以解决所有的问题。甚至解决一个小问题，很优秀的算法却不一定适合它

（马哲：民主不是包治百病的神药，具体情况需要具体分析，适合自己的才是最好的）

我感觉做梦时老马会来打我啊

三、算法的特性

算法具有五个基本特性：输入、输出、有穷性、确定性和可行性

1.输入输出

（1）算法具有零个或多个输入

（2）算法至少有一个或多个输出

2.有穷性

指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成

（注意：这里的有穷的概念并不是纯数学意义的，而是在实际应用中合理的、可以接受的“有边界”。你说你写一个算法，计算机需要算上个二十年，我怕你自己都等不了吧）

3.确定性

算法的每一步骤都具有确定的含义，不会出现二义性

（理解：算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果）

4.可行性

算法的每一步都必须是可行的，即每一步都能够通过执行有限次数完成

四、算法设计的要求

1.正确性（好的算法，起码是要正确的，连正确都谈不上，还谈什么？）

算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案

算法的“正确”通常在用法上有很大的差别，大体分为以下四个层次：

（1）算法程序没有语法错误

（2）算法程序对于合法的输入数据能够产生满足要求的输出结果

（3）算法程序对于非法的输入数据能够得出满足规格说明的结果

（4）算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果

层次1要求最低，但仅仅满足层次1谈不上好算法，就像仅仅解决温饱，不能算是生活幸福一样。而层次4最难，我们几乎不可能逐一验证所有的输入都得到正确的结果

故算法的正确性在大部分的情况下都不可能用程序来证明，而是用数学方法证明

证明一个复杂算法在所有层次上都正确的代价非常昂贵

故一般情况下，我们把层次3作为一个算法是否正确的标准

2.可读性（算法（也包括实现它的代码）好坏很重要的标志）

算法设计的另一目的是为了便于阅读、理解和交流

3.健壮性

当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果

4.时间效率高和存储量低

五、算法效率的度量方法

1.事后统计方法（缺陷很大，不予采纳）

这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低

很大缺陷：

（1）必须依据算法事先编制好程序，这通常需要花费大量的时间和精力。若编好后发现它根本是很糟糕的算法，那就白干咯

（2）时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣

（3）算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现

2.事前分析估算方法

在计算机程序编制前，依据统计方法对算法进行估算

经分析发现，一个高级语言编写的程序在计算机上运行时所消耗的时间取决于以下因素：

（1）算法采用的策略、方法

（2）编译产生的代码质量

（3）问题的输入规模

（4）机器执行指令的速度

第1条当然是算法好坏的根本

第2条要由软件来支持

第4条要看硬件性能

即抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模（问题输入规模是指输入量的多少）

测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比（我不管你每一步走多久，我只管你走了多少步）

最终，分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

六、函数的渐进增长

给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐快于g(n)

与最高次项相乘的常数并不重要，最高次项的指数大的，函数随着n的增大，结果也会变得增长特别快

结论：判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的。如果我们可以对比这几个算法的关键执行次数函数的渐进增长性，基本就可以分析出：某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法。这其实就是事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率

七、算法时间复杂度

1.定义

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

用大写O()来体现算法时间复杂度的记法，称之为大O记法

一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法

O(1)叫常数阶，O(n)叫线性阶，O()叫平方阶

2.推导大O阶方法

（1）用常数1取代运行时间中的所有加法常数

（2）在修改后的运行次数函数中，只保留最高阶项

（3）若最高阶项存在且不是1，则去除与这个项相乘的常数

得到的结果就是大O阶

3.常数阶

（1）定义：与问题的大小无关（n的多少），执行时间恒定的算法，称之为具有O(1)的时间复杂度，又叫常数阶

（2）注意：不管这个常数是多少，都记作O(1)，而不能是O(3)、O(12)等其他任何数字，这是初学者常犯的错误

（3）顺序结构和分支结构的时间复杂度都是O(1)（这里的分支结构指的是单纯的分支结构（不包含在循环结构中），对分支结构而言，无论是真，还是假，执行的次数都是恒定的，不会随着n的变大而发生变化）

4.线性阶

线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常需要确定某个特定语句或某个语句集运行的次数。故我们要分析算法的复杂度，关键就是要分析循环结构的运行情况

下面这段代码，它的循环的时间复杂度是O(n)，因为循环体中的代码必须要执行n次

int i;
for(i = 0; i < n; i++)
{
    /*时间复杂度为O(1)的程序步骤序列*/
}

5.对数阶

下面这段代码，时间复杂度为O(logn)（log底数为2，常省略）

int count = -1;
while (count < n)
{
    count = count * 2;
    /*时间复杂度为O(1)的程序步骤序列*/
}

由于每次count乘以2后，就距离n更近了。即，有多少个2相乘后大于n，则会退出循环。

由得到，故这个循环的时间复杂度为O(logn)

6.平方阶

下面代码是一个循环嵌套，它的内循环刚已分析过，时间复杂度为O(n)

总结：循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数 

经验：其实理解大O推导不算难，难的是对数列的一些相关运算，这更多的是考察你的数学知识和能力

测试：

计算下面这段代码的时间复杂度

 7.常见的时间复杂度

常见的时间复杂度如下图所示

8.最坏情况与平均情况 

 最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间

平均运行时间是所有情况中最有意义的，因为它是期待的运行时间。即我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的

对算法时间复杂度的分析：

（1）平均时间复杂度：计算所有情况的平均值

（2）最坏时间复杂度：计算最坏情况下的时间复杂度

注意：一般在没有特殊说明的情况下，都是指最坏时间复杂度

八、算法空间复杂度

1.引入

2.定义

3.原地工作

一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需存储对数据操作的存储单元

若输入数据所占空间只取决于问题本身，和算法无关，这样只需分析该算法在实现时所需的辅助单元即可

若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)

4.注意

通常都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。

当不用限定词地使用“复杂度”时，通常都是指时间复杂度

九、总结