数据结构与算法——算法复杂度
本文最后更新于 577 天前,其中的信息可能已经有所发展或是发生改变。

渐进记号

五种渐进记号

  • 大$O$记号:

对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量 $c$ 和 $n_{0}$,使得对所有 $n \geq n_{0}$,有 $0 \leq f(n) \leq cg(n)$成立。$f(n)$ 只有一个渐进上界,$f(n)$ 的阶不高于 $g(n)$ 的阶。

  • $\Omega$记号:

对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量 $c$ 和 $n_{0}$,使得对所有 $n \geq n_{0}$,有 $0 \leq cg(n) \leq f(n)$成立。$f(n)$ 只有一个渐进下界,$f(n)$ 的阶不低于 $g(n)$ 的阶。

  • $\Theta$记号:

对于给定函数 $g(n)$,$f(n)=\Theta(g(n))$:存在正常量 $c_{1}$,$c_{2}$ 和 $n_{0}$,使得对所有 $n \geq n_{0}$,有$0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)$ 成立。$\Theta$记号渐进地给出了一个函数的上界和下界,$f(n)$ 的阶等于 $g(n)$ 的阶

若$f(n)=O(g(n))$ 且 $f(n)= \Omega (g(n))$,则 $f(n)= \Theta (g(n))$。

  • 小$o$记号:

对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量 $c > 0$ 和 $n_{0} > 0$,使得对所有$n \geq n_{0}$,有$0 \leq f(n) < cg(n)$ 成立。$f(n)$ 只有一个渐进紧确上界,$f(n)$ 的阶低于 $g(n)$ 的阶。

  • $\omega$记号:

对于给定函数 $g(n)$,$f(n)=O(g(n))$:存在正常量 $c > 0$ 和 $n_{0} > 0$,使得对所有 $n \geq n_{0}$,有$0 \leq cg(n) < f(n)$ 成立。$f(n)$ 只有一个渐进紧确下界,$f(n)$ 的阶高于 $g(n)$ 的阶。

相关定理

  • 定理1:

(1)如果 $\lim_{n \to + \infty} \frac{f(n)}{g(n)}$存在,且为某个常数 $c$,则 $f(n)= \Theta (g(n))$
(2)如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}=0$,则$f(n)= O (g(n))$
(3)如果$lim_{n \to +\infty} \frac{f(n)}{g(n)}=\infty$,则$f(n)= \omega (g(n))$

由定理1可以导出两个重要结果:

(1)多项式函数的阶低于指数函数的阶:

$$n^{d}=o(r^{n}), \quad r > 1,d > 0$$

(2)对数函数的阶低于幂函数的阶:

$${\rm \ln}n=o(n^{d}), \quad d>0$$

  • 定理2,传递性:

若$f(n)= \Theta (g(n))$,且$g(n)=\Theta (h(n))$,则$f(n)=\Theta(h(n))$。对于大$O$、小$o$、$\Omega$、$\omega$同样成立。

  • 定理3:

$$f=O(h), \quad g=O(h) \rightarrow f+g=O(h)$$ 该性质可推广到有限个函数。算法由有限个步骤构成,若每一步的时间复杂度函数的上界都是$h(n)$,那么算法的时间复杂度函数可以写作$O(h(n))$

相关性质

  • 1、自反性:

$$f(n)=\Theta (f(n))$$
$$f(n)=O(f(n))$$
$$f(n)=\Omega(f(n))$$

  • 2、对称性:

$f(n)=\Theta(g(n))$,当且仅当$g(n)=\Theta(f(n))$

  • 3、转置对称性:

$f(n)=O(g(n))$当且仅当$g(n)=\Omega(f(n))$ $f(n)=o(g(n))$当且仅当$g(n)=\omega(f(n))$

几类重要函数

  • 至少指数函数级: $2^{n}$, $3^{n}$, $n!$, $2^{2^{n}}$, $n2^{n}$, $(\log n)^{\log n}=n^{\log \log n}$
  • 多项式级: $n$, $n^{2}$, $n {\rm \log}n$, $n^{\frac{1}{2}}$, $n^{3}$, ${\rm \log}(n!)=\Theta(n {\rm \log}n)$
  • 对数多项式级: ${\rm \log}n$, ${\rm \log}^{2}n$, ${\rm \log \log}n$, $\sqrt{\log n}$

取整函数

  • $\lfloor x \rfloor$:向下取整,$\lceil x \rceil$:向上取整
  • 一些性质:

$$x-1< \lfloor x \rfloor \leq x \leq \lceil x \rceil< x+1$$

$$\lfloor x+n \rfloor=\lfloor x \rfloor + n, \lceil x+n \rceil = \lceil x \rceil+ n$$

$$\left \lceil \frac{n}{2} \right \rceil + \left \lfloor \frac{n}{2} \right \rfloor= n$$

$$\left \lceil \frac{\left \lceil \frac{n}{a} \right \rceil}{b} \right \rceil = \left \lceil \frac{n}{a b} \right \rceil, \quad \left \lfloor \frac{\left \lfloor \frac{n}{a} \right \rfloor}{b} \right \rfloor = \left \lfloor \frac{n}{a b} \right \rfloor$$


参考资料

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇