算法分析设计-复杂度分析

评价标准：▶ 运行时间 ▶ 运算步骤 ▶ 增长量级

运行时间随机器而异，它是由机器本身软硬件环境决定的，与算法无关。我们更多的讨论影响运行时间的另一个因素—运算步骤。

① 什么是运算步骤？

基本运算（加，减，乘，除，余，判断，数组的读取，写入，函数调用等）发生的次数。

②优点

机器无关，具有解释力

③缺点

计数繁琐，求解有难度，函数复杂

④注意

算法复杂度主要考虑输入规模较大的情形，此时具体的增长函数不是那么重要，关键是其增长量级。

假设某算法的执行步骤 f(n) 跟输入的规模的关系为 f(n) = 3n²+150n+10000，影响最大的项为3n²。能否用n²表示？为什么？

基本可以，但是不完全可以。

为什么基本可以？

当n很大时，后面的项（增长速度慢）不重要。

为什么不完全可以？

只用n²表示不了后面的项，也表示不了系数。

① 增长量级的近似表示

下界（Big-Ω）：Ω(n²) 表示存在常数 c 使得当 n >= n₀ 时，cn² =< f(n)

上界（Big-O）：O(n²) 表示存在常数 c 使得当 n >= n₀ 时，cn² >= f(n)

确界（Big-θ）：θ(n²) 表示存在常数 c₁、c₂ 使得当 n >= n₀ 时，c₁n² <= f(n) <= c₂n²

② 常见的时间复杂度

③ 算法复杂度分析的三种情形

算法的运算次数并非固定不变，而有随机因素。如搜索，运气好一次找到，运气差最后找到。

例：从已经排好序的数组A中，查找某个数是否在A中，若在，返回其位置。

对于分治法：得到结果时，数据规模为1。此时应满足 n/2^t-1 = 1，t 表示比较次数。化简得到 t = log₂n+1。

比较次数	1	2	3	4	5
数据规模	n	n/2	n/4	n/2³	n/2⁴

枚举法和分治法分别的花费次数：

类型	BC	AC	WC
Brute force approach（枚举法）	1	n/2	n
Divide and conquer（分治法）	1	log₂n/2+1	log₂n+1

例子：斐波那锲数列迭代，递归的方式各自的时间复杂度。

迭代：O(n)

递归：O(2ⁿ) （实际上是二叉树的结点个数）

暂无