算法复杂度 ─ 直观定义

算法复杂度是算法运行所需要的计算机资源的量，需要时间资源的量称为时 间复杂性，需要的空间资源的量称为 空间复杂性

• 时间复杂度和空间复杂度是只依赖于算法求解的问题规模和算法输入的函数
• 𝑁、𝐼 分别表示算法求解的问题规模和算法输入，则算法的时间复杂度𝑇和空 间复杂度𝑆可以分别表示为:
  • 𝑇 = 𝑇(𝑁, 𝐼) 𝑆 = 𝑆(𝑁, 𝐼)

算法复杂度分析 ─ 指令抽象

T(N, I) 表示特定算法在一台抽象的计算机上运行所需要的时间

• K 个元运算，O1, O2, …, Ok, 运行一次所需时间为 t1, t2, …, tk;
• 统计 Oi 的调用次数为 ei，ei = ei(N, I);
• 因此，T(N, I) = ∑tiei(N, I)。
• 归纳逻辑: 从个别到一般

T(N) 的表达式比较复杂，需合理的简化!

对于算法 A 的复杂度函数𝑇(𝑁)，如果存在𝑇′(𝑁) ，使得当𝑁 → ∞时有 (𝑇𝑁 −𝑇′(𝑁))⁄𝑇(𝑁)→0，那么就称𝑇′(𝑁) 为算法 A 当𝑁→∞的渐近复杂性

• 𝑇′(𝑁) 是𝑇(𝑁) 略去低阶项所留下的主项，表达简单
• 如果两个算法的渐近复杂性的阶不相同，那么只要确定出各自的阶就可以判断哪一个算法效率高
• 阶跟𝑇′(𝑁) 中的常数因子没有关系，𝑇′(𝑁) 可进一步简化，省略常数因子

时间复杂度的记号包括:O Ω Θ

时间复杂度记号 O #

设 f(N) 和 g(N) 是定义在正数集上的正函数，如果存在正的常数 C 和自然数 N0，使得当 N≥N0 时有 f(N) ≤Cg(N)，则称函数 f(N) 当 N 充分大时上有界，g(N) 是 f(N) 的一个上界， 记为 f(N)=O(g(N))，即 f(N) 的阶不高于 g(N) 的阶。

• 注意
  • 不是直接比较 f(N) 和 g(N) 的数值大小
  • O 表示的只是一个充分大的上界，上界的阶越低则评估越精确，结果越有价值!

运算法则

• 1. O(f)+O(g)=O(max(f,g));
• 2. O(f)+O(g)=O(f+g);
• 3. O(f)O(g)=O(fg);
• 4. 如果 g(N)=O(f(N))，则 O(f)+O(g)=O(f);
• 5. O(Cf(N))=O(f(N))，其中 C 是一个正的常数;
• 6. f=O(f)

大 O 比率定理

对于函数 f(N) 和 g(N)，如果极限 lim 𝑓(𝑁)/𝑔(𝑁) 存在，则𝑓(𝑁) = 𝑂(𝑔 𝑁 ) 当且仅当存在正的常数 C，使得 lim 𝑓(𝑁)/𝑔(𝑁) ≤ 𝐶

时间复杂度记号 Ω #

Ω的定义: 如果存在正的常数 C 和自然数 N0，使得当 N3N0 时有 f(N)3Cg(N)，则称 函数 f(N) 当 N 充分大时下有界，且 g(N) 是它的一个下界，记为 f(N) = Ω(g(N))， 即 f(N) 的阶不低于 g(N) 的阶。

时间复杂度记号 Θ #

Θ的定义: 定义 f(N) = Θ(g(N)) 当且仅当 f(N)=O(g(N)) 且 f(N)= Ω(g(N))，此 时称 f(N) 与 g(N) 同阶。

定理 1: 对于多项式函数 𝑓 𝑁 = 𝑎+𝑁+ + 𝑎+,%𝑁+,% + ⋯ + 𝑎%𝑁 + 𝑎&，如果 𝑎+ > 0，则有: 𝑓 𝑁 =𝑂(𝑁+)，𝑓 𝑁 =𝛺(𝑁+)，𝑓 𝑁 =𝛩(𝑁+)

时间复杂度类别

时间复杂度分析 #

非递归算法 #

1. 确定关键操作: 可以是高级程序设计语言中的赋值、比较、算术运算、逻辑 运算、读写单个常量或单个变量等操作 (一般被看作是基本操作，并约定所 用的时间都是一个单位); 也可以是由常数个基本操作构成的程序块
2. 计算关键操作总的执行步数: 一般是数列和的形式。
3. 求解其渐进阶: 并用 O(.) 表示

递归算法 #

1. 分析递归程序的结构，确定每一逻辑块的时间复杂性， 非递归的程序块 (或者 子函数) 用非递归方法分析其复杂性; 递归函数的复杂性则跟据其输入规模递 归地表示。
2. 构造复杂度函数的递推方程
3. 求解递归方程和渐进阶，并用 O(.) 表示