算法概述
第一章
1.理解什么是程序,什么是算法,程序与算法的区别和内在联系
1.1算法
是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列,满足性质:
(1)输入:有外部提供的量作为算法的输入。
(2)输出:算法产生至少一个量作为输出。
(3)确定性:组成算法的每条指令是清晰,无歧义的
(4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的
1.2程序
- 程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。
- 例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。
- 操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
1.3程序和算法的区别
- 算法是解决问题的步骤;程序是算法的代码实现,算法要依靠程序来完成功能;程序需要算法作为灵魂
- 程序是结果,算法是手段*(为编写出好程序所使用的运算方法)。同样编写一个功能的程序,使用不同的算法可以让程序的体积、效率差很多。所以算法是编程的精华所在**
- 算法+数据结构=应用程序**。算法是程序设计的核心,算法的好坏很大程度上决定了一个程序的效率。一个好的算法可以降低程序运行的时间复杂度和空间复杂度。先选出一个好的算法,再配合以一种适宜的数据结构,这样程序的效率会大大提高
2.算法的性质,好的算法的标准
3.算法分析的要求,算法复杂性的依赖
-
n算法复杂性 = 算法所需要的计算机资源:
时间资源和空间资源
-
算法的时间复杂性T(n);
-
算法的空间复杂性S(n)。
-
其中n是问题的规模(输入大小)。
4.算法的计算复杂性概念
4.1非递归算法时间复杂性
4.2递归算法时间复杂性
4.3最优算法时间复杂度分析
-
问题的计算时间下界为W(f(n)),则计算时间复杂性为O(f(n))的算法是最优算法。
-
例如,排序问题的计算时间下界为W(nlogn),计算时间复杂性为O(nlogn)的排序算法是最优算法。
-
堆排序算法是最优算法。
5.算法渐近复杂性的数学表述及复杂度的计算
5.1算法渐近复杂性
-
T(n) ®¥ , as n ;
-
(T(n) - t(n) )/ T(n) ®0 ,as n;
-
t**(n)**是T(n)的渐近性态,为算法的渐近复杂性。
-
在数学上, t(n)是T(n)的渐近表达式,是T(n)略去低阶项留下的主项,比T(n) 简单。
-
例:T(n)=3N2+4NlogN+7 t(n)=3N2
5.2常见算法时间复杂性比较
常见时间复杂度
执行次数函数举例 | 阶 | 非正式术语 |
---|---|---|
12 | O(1) | 常数阶 |
2n+3 | O(n) | 线性阶 |
3n2+2n+1 | O(n2) | 平方阶 |
5log2n+20 | O(logn) | 对数阶 |
2n+3nlog2n+19 | O(nlogn) | nlogn阶 |
6n3+2n2+3n+4 | O(n3) | 立方阶 |
2n | O(2n) | 指数阶 |
注意,经常将log2n(以2为底的对数)简写成logn
常见时间复杂度之间的关系
所消耗的时间从小到大
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
90802007427)]
所消耗的时间从小到大
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)