算法的复杂度的渐近表示方法 Big O Notation and More 吕云哲
主要内容 01 02 03 04 基础知识 详细定义 图形表示 实际使用 Contents 函数的阶——直观表示 数学定义及两两区别 形象化表示 04 实际使用 为什么常使用Big O
基础知识 函数的阶 设𝑎>1, 𝜇>0. 则𝑥→+∞时, log𝑎𝑥、𝑥𝜇、𝑎𝑥、𝑥𝑥皆为正无穷大量, 但增长速度大不同。孰疾孰缓? 答曰：𝒂>𝟏,𝝁>𝟎,𝒏→+∞时， 𝐥𝐨𝐠 𝒂 𝒏 ≪ 𝒏 𝝁 ≪ 𝒂 𝒏 ≪𝒏!≪ 𝒏 𝒏 南京大学数学教师 秦理真
∀𝑘>0,∃ 𝑛 0 ,∀𝑛> 𝑛 0 , 𝑓 𝑛 ≤𝑘∙𝑔 𝑛 详细定义: O 和 o 表达式 数学定义 极限表示 lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 =0 𝑓 𝑛 =𝑜 𝑔 𝑛 ∀𝑘>0,∃ 𝑛 0 ,∀𝑛> 𝑛 0 , 𝑓 𝑛 ≤𝑘∙𝑔 𝑛 无论𝑘取何值，在某一点 𝑛 0 后，𝑔(𝑛)都比𝑓(𝑛)“变化快” 𝑓(𝑛)“远小于”𝑔(𝑛) lim 𝑛→∞ sup 𝑓 𝑛 𝑔 𝑛 <∞ 𝑓 𝑛 =𝑂 𝑔 𝑛 ∃𝑘>0, ∃ 𝑛 0 ,∀𝑛> 𝑛 0 , 𝑓 𝑛 ≤𝑘∙𝑔 𝑛 存在𝑘的取值，在某一点 𝑛 0 后，𝑔(𝑛) 比𝑓(𝑛)“变化快” 𝑓(𝑛)不是“远大于”𝑔(𝑛) 总结： 小o相对紧缩，相当于“小于” 大O更加宽泛，相当于“不大于”
∀𝑘>0,∃ 𝑛 0 ,∀𝑛> 𝑛 0 , 𝑓 𝑛 ≥𝑘∙ 𝑔 𝑛 详细定义: Ω 和 ω 表达式 数学定义 极限表示 lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 =∞ 𝑓 𝑛 =𝜔 𝑔 𝑛 ∀𝑘>0,∃ 𝑛 0 ,∀𝑛> 𝑛 0 , 𝑓 𝑛 ≥𝑘∙ 𝑔 𝑛 无论𝑘取何值，在某一点 𝑛 0 后，𝑔(𝑛)都比𝑓(𝑛)“变化慢” 𝑓(𝑛)“远大于”𝑔(𝑛) lim 𝑛→∞ inf 𝑓 𝑛 𝑔 𝑛 >0 𝑓 𝑛 =𝛺 𝑔 𝑛 ∃𝑘>0,∃ 𝑛 0 ,∀𝑛> 𝑛 0 ,𝑓 𝑛 ≥𝑘∙𝑔 𝑛 存在𝑘的取值，在某一点 𝑛 0 后，𝑔(𝑛) 比𝑓(𝑛)“变化慢” 𝑓(𝑛)不是“远小于”𝑔(𝑛) 总结： 小ω相对紧缩，相当于“大于” 大Ω更加宽泛，相当于“不小于”
∃ε>0,∃ n 0 ,∀n> n 0 , 𝑓 𝑛 𝑔 𝑛 −1 <ε lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 =1 详细定义: Θ 和 θ(~) 表达式 数学定义 极限表示 ∃ε>0,∃ n 0 ,∀n> n 0 , 𝑓 𝑛 𝑔 𝑛 −1 <ε lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 =1 𝑓 𝑛 =𝜃 𝑔 𝑛 𝑓 𝑛 ~𝑔 𝑛 这是极限的定义！ 二者在极限时“相等” ∃ k 1 >0,∃ k 2 >0,∃ n 0 ,∀n> n 0 , k 1 ∙g(n)≤f(n)≤ k 2 ∙g(n) 𝑓 𝑛 =𝑂 𝑔 𝑛 𝑓(𝑛)=𝛺(𝑔(𝑛)) 𝑓 𝑛 =Θ 𝑔 𝑛 存在 𝑘 1 , 𝑘 2 的取值，在 𝑛 0 后，𝑔(𝑛) 把𝑓(𝑛)“架着走” 同时满足前两个条件 总结：都要求最高阶数相同 小θ最高阶系数也要一样，相当于“相等” 大Θ容许最高阶系数的大小不同，相当于“相似”
O o Θ ~ Ω ω 图形表示 边界（二者同阶） 都包含在内（实线） 不包含边界（虚线） 没有交集 二者有交集（同阶的函数） f(n)
问：为什么大多数时候选用大O反映算法的复杂度？ 实际使用 问：为什么大多数时候选用大O反映算法的复杂度？ 为什么不用Ω和ω？ 他们反映了算法消耗的下限，即最好的情况下会怎样，但是并不可能永远都是最好的情况。这样的描述方式会留下潜在的“时间超限”“内存超限”隐患。 为什么不用Θ和~？ 其实这样的描述最为精确，主要的问题在于方程的复杂程度。有些算法（例如插入排序）相同长度的样例下，时间复杂度可能天差地别，难以精确精确量化。如果可以，形式也会相当繁琐，不利于比较。 为什么不用o？ o不包含同阶，算法复杂度函数𝑓 𝑛 ∉𝑜(𝑔(𝑛))，因此不便于表示。 O有什么好处？ 描述最坏情况，相当于“保底”，得出的算法复杂度结果更加可靠，同时形式相对简洁。
谢谢 Thank You 吕云哲