渐近分析与复杂度

算法复杂度 ─ 直观定义

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

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

T(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) 的阶。

运算法则

大 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(.) 表示