Skip to content
Notes

第一章

简单的例题

10 位，可以表示 1024 个编号，分别是 00 0000 0000B 到 11 1111 1111B

1024 > 1000

00 0000 0000
...
11 1110 0111
  • 0 号喝 1x xxxx xxxx
  • 1 号喝 x1 xxxx xxxx
  • …
  • 9 号喝 xx xxxx xxx1

时间复杂度

渐近上界记号 O

O(g(n))={f(n)∣∃ c,n0>0,s.t.∀n⩾n0,0⩽f(n)⩽cg(n)}\displaystyle{ O \left( g \left( n \right) \right) = \left\lbrace f \left( n \right) \mid \exists \, c , n _{ 0 } > 0 , \text{s.t.} \forall n \geqslant n _{ 0 } , 0 \leqslant f \left( n \right) \leqslant c g \left( n \right) \right\rbrace }
  • 100n2∈O(n2)\displaystyle{ 100 n ^{ 2 } \in O \left( n ^{ 2 } \right) }
  • n/2∈O(n2)\displaystyle{ n {/} 2 \in O \left( n ^{ 2 } \right) }

非渐近紧确上界记号 o

o(g(n))={f(n)∣∀c>0,∃ n0>0,s.t.∀n⩾n0,0⩽f(n)<cg(n)}\displaystyle{ o \left( g \left( n \right) \right) = \left\lbrace f \left( n \right) \mid \forall c > 0 , \exists \, n _{ 0 } > 0 , \text{s.t.} \forall n \geqslant n _{ 0 } , 0 \leqslant f \left( n \right) { \color{red} < } c g \left( n \right) \right\rbrace } lim⁡n→∞f(n)g(n)=0\displaystyle{ \lim _{ n \to \infty } \frac{ f \left( n \right) }{ g \left( n \right) } = 0 }

渐近下界记号 Ω\Omega

Ω(g(n))={f(n)∣∃ c,n0>0,s.t.∀n⩾n0,0⩽cg(n)⩽f(n)}\displaystyle{ \Omega \left( g \left( n \right) \right) = \left\lbrace f \left( n \right) \mid \exists \, c , n _{ 0 } > 0 , \text{s.t.} \forall n \geqslant n _{ 0 } , 0 \leqslant c g \left( n \right) \leqslant f \left( n \right) \right\rbrace }
  • 100n2∈Ω(n2)\displaystyle{ 100 n ^{ 2 } \in \Omega \left( n ^{ 2 } \right) }
  • n2/2∈Ω(n)\displaystyle{ n ^{ 2 } {/} 2 \in \Omega \left( n \right) }

非渐近紧确下界渐近记号 ω\displaystyle{ \omega }

ω(g(n))={f(n)∣∀c>0,∃n0>0,s.t.∀n⩾n0,0⩽cg(n)<f(n)}\displaystyle{ \omega \left( g \left( n \right) \right) = \left\lbrace f \left( n \right) \mid \forall c > 0 , \exists n _{ 0 } > 0 , \text{s.t.} \forall n \geqslant n _{ 0 } , 0 \leqslant c g \left( n \right) { \color{red} < } f \left( n \right) \right\rbrace } lim⁡n→∞f(n)g(n)=∞\displaystyle{ \lim _{ n \to \infty } \frac{ f \left( n \right) }{ g \left( n \right) } = \infty } f(n)∈ω(g(n))  ⟺  g(n)∈o(f(n))\displaystyle{ f \left( n \right) \in \omega \left( g \left( n \right) \right) \iff g \left( n \right) \in o \left( f \left( n \right) \right) }

渐近紧确界记号 Θ\Theta

Θ(g(n))={f(n)∣∃ c1,c2,n0>0,∀n⩾n0,0⩽c1g(n)⩽f(n)⩽c2g(n)}\displaystyle{ \Theta \left( g \left( n \right) \right) = \left\lbrace f \left( n \right) \mid \exists \, c _{ 1 } , c _{ 2 } , n _{ 0 } > 0 , \forall n \geqslant n _{ 0 } , 0 \leqslant c _{ 1 } g \left( n \right) \leqslant f \left( n \right) \leqslant c _{ 2 } g \left( n \right) \right\rbrace }
  • n2/2−2n∈Θ(n2)\displaystyle{ n ^{ 2 } {/} 2 - 2 n \in \Theta \left( n ^{ 2 } \right) }
f(n)∈Θ(g(n))  ⟺  f(n)∈O(g(n)) and f(n)∈Ω(g(n))\displaystyle{ f \left( n \right) \in \Theta \left( g \left( n \right) \right) \iff f \left( n \right) \in O \left( g \left( n \right) \right) \text{ and } f \left( n \right) \in \Omega \left( g \left( n \right) \right) }

复杂度的排序

1≺log⁡log⁡n≺log⁡n≺n≺n3/4≺nlog⁡n≺n2≺2n≺n!≺2n2\displaystyle{ 1 \prec \log \log n \prec \log n \prec \sqrt{ n } \prec n ^{ 3 {/} 4 } \prec n \log n \prec n ^{ 2 } \prec 2 ^{ n } \prec {n !} \prec 2 ^{ n ^{ 2 } } }
渐近符号算数符号
O\displaystyle{ O }⩽\displaystyle{ \leqslant }
Ω\displaystyle{ \Omega }⩾\displaystyle{ \geqslant }
Θ\displaystyle{ \Theta }=\displaystyle{ = }
o\displaystyle{ o }<\displaystyle{ < }
ω\displaystyle{ \omega }>\displaystyle{ > }