Home
/
...
/
Introduce to Algorithm
/
三.算法评估(渐进符号)
Search
Try Notion
三.算法评估(渐进符号)
一.渐进符号
渐进符号的定义
渐进紧确界: Θ(g(n))={f(n):存在常量c1 c2使得n≥n0时候,有0≤c1g(n)≤f(n)≤c2g(n)}\Theta (g(n)) = \{ f(n) : 存在常量c_1\ c_2 使得 n≥ n_0 时候,有 0≤c_1g(n)≤f(n)≤c_2g(n) \}
渐进上界: O(g(n))={f(n):存在常量c2使得n≥n0时候,有0≤f(n)≤c2g(n)}O (g(n)) = \{ f(n) : 存在常量 c_2 使得 n≥ n_0 时候,有 0≤f(n)≤c_2g(n) \}
渐进下界: Ω(g(n))={f(n):存在常量c1使得n≥n0时候,有0≤c1g(n)≤f(n)}\Omega (g(n)) = \{ f(n) : 存在常量c_1 使得 n≥ n_0 时候,有 0≤c_1g(n)≤f(n)\}
非渐进确紧上界: o(g(n))={f(n):任意c2>0使得n≥n0时候,有0≤f(n)≤c2g(n)}o (g(n)) = \{ f(n) : 任意 c_2>0 使得 n≥ n_0 时候,有 0≤f(n)≤c_2g(n) \}
非渐进确紧下界: ω(g(n))={f(n):任意c1>0使得n≥n0时候,有0≤c2g(n)≤f(n)}\omega (g(n)) = \{ f(n) : 任意 c_1>0 使得 n≥ n_0 时候,有 0≤c_2g(n)≤f(n) \}
渐进符号的性质
传递性:
f=Θg=Θhf \overset{\Theta}{=} g \overset{\Theta}{=} h
f≤Og≤Ohf \overset{O}{≤} g \overset{O}{≤} h 其中 f≤Ogf \overset{O}{≤} g  表示 f=O(g)f=O(g)
f≥Ωg≥Ωhf \overset{\Omega}{≥} g \overset{\Omega}{≥} h
f<og<ohf \overset{o}{<} g \overset{o}{<} h f>ωg>ωhf \overset{\omega}{>} g \overset{\omega}{>} h
对称性:
f=Θg⟺g=Θff \overset{\Theta}{=} g \Longleftrightarrow g \overset{\Theta}{=} f
f≤Og⟺g≥Ωff \overset{O}{≤} g \Longleftrightarrow g \overset{\Omega}{≥} f
f<og⟺g>ωff \overset{o}{<} g \Longleftrightarrow g \overset{\omega}{>} f
无三分性
虽然借用了≥ = ≤号(比较运算符),但不具备实数系的三分性
即a与b 一定是上面提到的三种关系之一 a>b a<b a=b
比如nn与n1+sin(n)n^{1+sin(n)} 显然不属于 O o Ω ω Θ O\ o\ \Omega \ \omega \ \Theta \ 任意一种
渐进符号运算律
🤔渐进符号运算律-替代包括律: 将O(h)O(h)用K∗hK*h替代(k为常数),在最后的结果再用中用O(...)O(...)包括
例子: 来源于堆排序中Heap-Bulid T(n)分析
T(n)=∑h=0⌊log2n⌋⌈n2h+1⌉O(h)=O(n∑h=0⌊log2n⌋h2h)=O(n∑h=0∞h2h)=O(n)T(n) = \sum\limits_{h=0}^{\lfloor log_2n \rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h) = O(n\sum\limits_{h=0}^{\lfloor log_2n \rfloor}\frac{h}{2^h}) = O(n\sum\limits_{h=0}^{\infty}\frac{h}{2^h})=O(n)
二.常用函数及其性质
取整数除法运算
将⌈?b⌉将\lceil \frac{?}{b} \rceil作为一整个运算
同一般除法一样, 结合性(可以先计算a*b)
⌈⌈x/a⌉b⌉=⌈xab⌉\lceil \frac{\lceil x/a \rceil}{b} \rceil = \lceil \frac{x}{ab} \rceil
⌊⌊x/a⌋b⌋=⌊xab⌋\lfloor \frac{\lfloor x/a \rfloor}{b} \rfloor = \lfloor \frac{x}{ab} \rfloor
常见函数复杂度比较
lga(n)<onb<ocnlg^a(n) \overset{o}{<} n^b \overset{o}{<} c^n
其中a b c为任意大于1的数
lg为任意底数,若不关心底数的对数函数也可写成lg(n)lg(n)
知道左边证明右边
若已知nb<ocnn^b \overset{o}{<} c^n 令lg(n 替换n) ,则有 lgb(n)<oclg(n)lg^b (n)\overset{o}{<} c^{lg(n)}
则有lgb(n)<oclg(n)=(底数a)lg(n)<nalg^b (n)\overset{o}{<} c^{lg(n)} = (底数^a)^{lg(n)} < n^a 证明了左边
对数函数
定义: 指数=底数对数对数=log⁡底数指数指数 = 底数^{对数}\quad 对数=\log_{底数}{指数}
在同样的底数下,指数对数一一对应,以指数为代表称数.
对数相除   ⟺  \iff 指数作为对数操作数
观点1(除法看待): t=log⁡ab=log⁡cblog⁡cat = \log_{a}{b}=\frac{\log_{c}{b}}{\log_{c}{a}}
观点2(指数 对数关系): a(t1/t2)=alogdt2dt1=alogb1b2a^(t_1/t_2) = a^ {log_{d^{t_2}}{d^{t_1}}} = a ^{log_{b1}{b2}} 其中b1b2b_1 b_2为任意底(底任意) 对数取t1t2t_1 t_2的数
同指数 不同底数 ⇒导致的不同对数
推导1
b=at1=ct2b = a^{t_1} = c^{t_2}
t1=log⁡abt_1 = \log_{a}{b}
t2=log⁡cbt_2 = \log_{c}{b}
t1/t2=log⁡ablog⁡cb=1/log⁡ba1/log⁡bc=log⁡act_1/t_2 = \frac{\log_{a}{b}}{\log_{c}{b}} =\frac{1/\log_{b}{a}}{1/\log_{b}{c}}= \log_{a}{c}
🤔推导2(除法增加一项减少一项 规律)
log⁡acb=log⁡aca∗log⁡ab\log_{ac}{b} = \log_{ac}{a}* \log_{a}{ b } 
根据log⁡ab=log⁡cblog⁡ca\log_{a}{b}=\frac{\log_{c}{b}}{\log_{c}{a}}可证明
alog⁡bc=alog⁡ac∗log⁡ba=clog⁡baa^{\log_{b}{c}} = a^{\log_{a}{c}*\log_{b}{a}} =c^{\log_{b}{a}} (交换a c)