数学基础

增长的阶增长函数同阶函数集合 θ（渐进非负）低阶函数集合 O （只有一个渐进上界）高阶函数集合 Ω（渐进下界）严格低阶函数集合 o严格高阶函数集合 w 和式的估计和界限递归方程补充练习题

增长的阶

描述算法效率？增长率忽略低阶项，保留高阶项；忽略常系数θ插入排序最坏运行时间θ(n²)

增长函数

同阶函数集合 θ（渐进非负）

例如，证明1/2n²-3n=θ(n²)： c₁n²<=1/2n²-3n<=c₂n² c₁<=1/2-3/n<=c₂ 对于∀n>=1,c₂>=1/2，且对于∀n>=7，c₁<=1/14 因此c₁=1/14，c₂=1/2，n₀=7

低阶函数集合 O （只有一个渐进上界）

f(n)=θ(g(n)) => f(n)=O(g(n))θ标记（渐进紧界）强于O标记（渐进上界）an+b=O(n²)？没有高阶项；n=O(n²)同理θ(g(n))∈O(g(n))f(n)=O(n^k) <=> f(n)是多项式界限的

高阶函数集合 Ω（渐进下界）

f(n)=θ(g(n)) <=> f(n)=O(g(n))且f(n)=Ω(g(n))Ω用来描述运行时间最好情况，对所有输入都正确，∴最好运行时间=运行时间≠最坏运行时间

严格低阶函数集合 o

例如，证明2n=o(n²)： 对∀c>0，要使2n<cn²，必要满足2/c<n。 ∴n₀=2/c时，2n<cn²对∀c>0，n>n₀成立

o标记用于标记上界但不是紧的情况f(n)=o(g(n)) => lim_n->∞f(n)/g(n)=0

严格高阶函数集合 w

f(n)=w(g(n)) <=> g(n)=o(f(n))

SUMMURY 传递性：θ O Ω o w （对同一种符号） 自反性：θ O Ω f(n)=θ(f(n)) 对称性：θ f(n)=θ(g(n)) <=> g(n)=θ(f(n)) 反对称性： f(n)=w(g(n)) <=> g(n)=o(f(n)) f(n)=Ω(g(n)) <=> g(n)=O(f(n))

和式的估计和界限

通过上界和下界描述时间复杂度 线性和 ∑(ca_k+b_k)=c∑a_k+∑b_k级数 ∑n=n（n+1）/2=θ（n²） ∑xⁿ=（xⁿ⁺¹）/（x-1）【n趋于∞时，1/（1-x）】 调和级数H_n=∑1/n=lnn+O（1） etc…和的界限 例如，证明∑3^k=O（3ⁿ） 【用O的定义】 直接求界限： 1）放大 2）max/min 3）∑a_k<=∑a₀r^k=a₀∑r^k=a₀/（1-r） 4）分裂和 f(x)递减时，∫(m->n+1) f(x)dx <= ∑n|k=m <= ∫(m-1->n) f(x)dx

递归方程

最小输入值描述方程/不等式求解方法

1）替换：先猜想，再用数归

---

例如，求解2T(n/2+17)+n 猜测T(n)=O(nlgn)，证明**（数归）**

---

2）迭代：转化成和式，估计和

---

令n/4ⁱ=1，∴i=log₄n T(n)=

---

3）master定理：T(n)=aT(n/b)+f(n)

---

设常数a>=1,b>1，函数f(n)，T(n)是定义在非负整数集上的函数T(n)=aT(n/b)+f(n)。T(n)可以如下求解： 红色部分无法受用master定理

例如，求解T(n)=9T(n/3)+n 解：a=9，b=3，f(n)=n，n^logb(a)=θ(n²) ∵f(n)=n=O(n^logb(a)-ε)，ε=1 ∴T(n)=θ(n^logb(a))=θ(n²)

再例，求解T(n)=T(2n/3)+1 解：a=1，b=3/2，f(n)=1，n^logb(a)=θ(n^log3/2(1))=n⁰=1 f(n)=1=θ(1)=θ(n^logb(a))，T(n)=θ(n^logb(a)·lgn)=θ(lgn)

再例，求解T(n)=3T(n/4)+nlgn 解：a=3，b=4，f(n)=nlgn，n^logb(a)=O(n^0.973) 1）f(n)=nlgn>=n=n^logb(a)-ε，ε≈0.2 2）对所有n，af(n/b)=3*(n/4)lg(n/4)=(3/4)nlg(n/4)<=(3/4)nlgn=cf(n)，c=3/4。于是T(n)=θ(f(n))=θ(nlgn)

---

补充

任意正的多项式函数都比任意多对数增长得快常见阶的高低 n!>2ⁿ>多项式>log>常数（多项式看最大幂指数）时间复杂度常用：O、θ问题复杂度常用：Ωf(n)+o(f(n)) = θ(f(n))证明或证否？ 看o(f(n)) 函数+函数 × 函数+集合 √上界不唯一，上确界唯一 （证明时不需要是紧界）master定理的多项式大于指的是？ 相除后相差一个n^εT(f(n)+c)的常数c

练习题