数据结构 408-1-2

# 什么是算法

程序 = 数据结构 + 算法

数据结构：如何用数据正确地描述现实世界的问题，并存入计算机

算法：如何高效地处理这些数据，以解决实际问题

• 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

# 算法的特性

• 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可以在有穷时间内完成

  • 算法必须是有穷的，而程序可以是无穷的

• 确定性。算法中每条指令必须由确切含义，对于相同输入只能得出相同的输出

• 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

• 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合

• 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量

# “好” 算法的特质

• 正确性。算法应能正确地解决求解问题
• 可读性。算法应具有良好的可读性。以帮助人们理解
• 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名奇妙的输出结果
• 高效率与低存储量需求。及低时间复杂度与低空间复杂度

# 时间复杂度

事先预估算法时间开销 T (n) 与问题规模 n 的关系

计算式考虑阶数最高的部分

• O 表示 “同阶”，同等数量级。即当$n\rightarrow\infin$ 时，二者之比为常数

加法规则：

$$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$$

• 多项相加，只保留最高阶的项，且系数变为 1

乘法规则：

$$T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$$

• 多项相乘，都保留

$$O(1)<O(log_2n)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(n!)<O(n^n)$$

结论 1：顺序执行的代码只会影响常数项，可以忽略

结论 2：只需挑循环中的一个基本操作分析它的执行次数与 n 的关系即可

结论 3：如果由多层嵌套循环，只需关注最深层循环循环了几次

• 最坏时间复杂度：最坏情况下算法的时间复杂度
• 平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望时间
• 最好时间复杂度：最好情况下算法的时间复杂度

# 空间复杂度

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为 S (n)=O (1)

算法原地工作 —— 算法所需内存空间为常量

空间复杂度计算一样服从加法规则和乘法规则

普通程序计算：

• 找到所占空间大小与问题规模相关的变量
• 分析所占空间 x 与问题规模 n 的关系 x=f (n)
• x 的数量级 O (x) 就是算法空间复杂度 S (n)

递归程序计算：

• 找到递归调用的深度 x 与问题规模 n 的关系 x=f (n)
• x 的数量级 O (x) 就是算法空间复杂度 S (n)
• 注：有的算法各层函数所需存储所需存储空间不同，分析方法略有区别