E算法的复杂度的渐近表示方法BigONotationandMore
算法的复杂度的渐近表示方法 Big O Notation and More
主要内容Contents详细定义基础知识数学定义及两两区别函数的阶一一直观表示图形表示实际使用形象化表示为什么常使用Bigo
基础知识 函数的阶——直观表示 主要内容 Contents 图形表示 形象化表示 详细定义 数学定义及两两区别 实际使用 为什么常使用Big O
E基础知识函数的阶设a>1,μ>0.则x→+8时，logax、x、α、x*皆为正无穷大量但增长速度大不同。熟疾熟缓？答日:a>1,μ>0,n→+oo时,logan<n<an<n!<n"Big-oComplexity10000(1)900800O(logn)7000(n)600500-o(nlogn)soo0(nA2)300200O(2^n)100O(nl)O010203040607080100n9tlements
基础知识 函数的阶 设𝑎>1, 𝜇>0. 则𝑥→+∞时, log𝑎𝑥、𝑥 𝜇 、𝑎 𝑥 、𝑥 𝑥皆为正无穷大量, 但增长速度大不同。孰疾孰缓? 答曰：𝒂 > 𝟏, 𝝁 > 𝟎, 𝒏 → +∞时，𝐥𝐨𝐠𝒂𝒏 ≪ 𝒏 𝝁 ≪ 𝒂 𝒏 ≪ 𝒏! ≪ 𝒏 𝒏
B详细定义：0和0表达式数学定义极限表示f(n)0f(n) = o(g(n))limVk > 0,Eno, Vn >no,lf(n)/ ≤ k.g(n)n= g(n)无论k取何值，在某一点no后，g(n)都比f(n）“变化快f(n)“远小于"g(n)If(n)If(n) = 0(g(n)limsup3k > 0,Eno,Vn > no,lf(n)/ ≤k· g(n)8g(n)n-存在k的取值，在某一点no后，g(n)比f(n）"变化快f(n）不是“远大于"g(n)总结：小相对紧缩，相当于“小于”大0更加宽泛，相当于“不大于
详细定义: O 和 o 𝑓 𝑛 = 𝑜 𝑔 𝑛 𝑓 𝑛 = 𝑂 𝑔 𝑛 ∀𝑘 > 0,∃𝑛0 , ∀𝑛 > 𝑛0 , 𝑓 𝑛 ≤ 𝑘 ∙ 𝑔 𝑛 ∃𝑘 > 0, ∃𝑛0 , ∀𝑛 > 𝑛0 , 𝑓 𝑛 ≤ 𝑘 ∙ 𝑔 𝑛 lim 𝑛→∞ sup 𝑓 𝑛 𝑔 𝑛 < ∞ lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 = 0 无论𝑘取何值，在某一点𝑛0后，𝑔(𝑛)都比𝑓(𝑛)“变化快” 存在𝑘的取值，在某一点𝑛0后，𝑔(𝑛) 比𝑓(𝑛)“变化快” 𝑓(𝑛)“远小于”𝑔(𝑛) 𝑓(𝑛)不是“远大于”𝑔(𝑛) 总结： 小o相对紧缩，相当于“小于” 大O更加宽泛，相当于“不大于” 表达式 数学定义 极限表示
B详细定义：2和w表达式数学定义极限表示[f(n)f(n) = w(g(n))limVk > 0,Eno, Vn > no,If(n)/ ≥ k.Ig(n)I8g(n)n-→00无论k取何值，在某一点no后，g(n)都比f(n）“变化慢f(n)"远大于"g(n)f(n)inf0f(n) = 2(g(n)limi3k > 0,Eno, Vn > no,f(n) ≥ k · g(n)g(n)n-0存在k的取值，在某一点no后，g(n）比f（n）"变化慢f(n）不是“远小于"g(n)总结：小w相对紧缩，相当于“大于”大2更加宽泛，相当于“不小于
详细定义: Ω 和 ω 𝑓 𝑛 = 𝜔 𝑔 𝑛 𝑓 𝑛 = 𝛺 𝑔 𝑛 ∀𝑘 > 0,∃𝑛0 , ∀𝑛 > 𝑛0 , 𝑓 𝑛 ≥ 𝑘 ∙ 𝑔 𝑛 ∃𝑘 > 0, ∃𝑛0 , ∀𝑛 > 𝑛0 , 𝑓 𝑛 ≥ 𝑘 ∙ 𝑔 𝑛 lim 𝑛→∞ inf 𝑓 𝑛 𝑔 𝑛 > 0 lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 = ∞ 无论𝑘取何值，在某一点𝑛0后，𝑔(𝑛)都比𝑓(𝑛)“变化慢” 存在𝑘的取值，在某一点𝑛0后，𝑔(𝑛) 比𝑓(𝑛)“变化慢” 𝑓(𝑛)“远大于”𝑔(𝑛) 𝑓(𝑛)不是“远小于”𝑔(𝑛) 总结： 小ω相对紧缩，相当于“大于” 大Ω更加宽泛，相当于“不小于” 表达式 数学定义 极限表示