算法设计与分析知识点

第一章基础知识

1.算法的定义

算法就是解决问题的方法，是解决某一特定问题的一组有穷指令的序列，是完成一个任务所需要的具体步骤和方法

2.算法的特征

有限性 一个算法总是在执行了有穷步的运算之后终止

确定性：算法的每种运算必须要有确切的定义，不能有二义性。输入：每个算法有0个或多个输入。所谓0个输入是指算法本身定出了初始条件。

输出：一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量

可行性：算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。（实数的算术运算是“不能行”的）

3.计算过程

只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则

4.算法的有穷性意味着不是所有的计算机程序都是算法

5.算法正确性证明

数学归纳法，反例：能够使算法运行失败的输入实例

6.算法的好坏：

通过数学方法进行分析，时间复杂度，空间复杂度，循环次数（归并，快排，贪心的复杂度）

7.算法运行中主要影响运行时间的语句是基本操作，即占有最多比例的语句

8.时间复杂度分析：

1）确定用来表示问题规模的变量；

2）确定算法的基本操作；

3）写出基本操作执行次数的函数（运行时间函数）；

4）如果函数依赖输入实例，则分情况考虑：最坏情况、最好情况、平均情况；

5）只考虑问题的规模充分大时函数的增长率，用渐近符号O 、Θ、Ω 、o 来表示。

6）常用O和Θ

9.基本操作

算法中的某个初等操作，基本操作的选择，必须反映出该操作随着输入规模的增加而变化的情况