• 欢迎访问最初的梦想
  • Github https://github.com/anthonyzhai

函数的增长

编程 AnthonyZhai 2个月前 (08-11) 70次浏览 已收录 0个评论

通过定义确定渐近记号

1 $\Theta$ —— 同等量级

  若$f(n)和g(n)$满足$\exists 正常量c_1,c_2和n_0, 使得 \forall n \geq n_0, 有0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$,则称$g(n)是f(n)$的一个渐近紧确界(asymptotically tight bound),记做$f(n)=\Theta(g(n))$。

1.1 $O$ —— 上界

  若$f(n)和g(n)$满足$\exists 正常量c和n_0, 使得 \forall n \geq n_0, 有0 \leq f(n) \leq cg(n)$,则称$g(n)是f(n)$的一个渐近上界,记做$f(n)=O(g(n))$。

1.2 $\Omega$ —— 下界

  若$f(n)和g(n)$满足$\exists 正常量c和n_0, 使得 \forall n \geq n_0, 有0 \leq cg(n) \leq f(n)$,则称$g(n)是f(n)$的一个渐近下界,记做$f(n)=\Omega(g(n))$。

1.3 $o$ —— 严格上界

  若$f(n)和g(n)$满足$\forall 正常量c>0, \exists 正常量n_0>0, 使得 \forall n \geq n_0, 有0 \leq f(n) \leq cg(n)$,则称$g(n)是f(n)$一个非渐近紧确上界,记做$f(n)=o(g(n))$。

1.4 $\omega$ —— 严格下界

  若$f(n)和g(n)$满足$\forall 正常量c>0, \exists 正常量n_0>0, 使得 \forall n \geq n_0, 有0 \leq cg(n) \leq f(n)$,则称$g(n)是f(n)$一个非渐近紧确下界,记做$f(n)=\omega(g(n))$。

下图分别显示了$\Theta, O, \Omega$记号定义的示意图。

函数的增长

2 比较函数

2.1 传递性

$$
f(n)=\Theta(g(n))且g(n)=\Theta(h(n)) \Rightarrow f(n)=\Theta(h(n)) \\
f(n)=O(g(n))且g(n)=O(h(n)) \Rightarrow f(n)=O(h(n)) \\
f(n)=\Omega(g(n)) 且 g(n)=\Omega(h(n)) \Rightarrow f(n)=\Omega(h(n)) \\
f(n)=o(g(n))且g(n)=o(h(n)) \Rightarrow f(n)=o(h(n)) \\
f(n)=\omega(g(n))且g(n)=\omega(h(n)) \Rightarrow f(n)=\omega(h(n))
$$

2.2 对称性

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

3 标准记号和常用函数

3.1 向下取整、向上取整和四舍五入

使用$\left\lfloor x \right\rfloor$表示小于或等于$x$的最大整数,用$\left\lceil x \right\rceil$表示大于或等于$x$的最小整数,用$[x]$表示$x$的四舍五入的结果。

3.2 模运算

使用$a \equiv b(mod n)$表示模$n$时$a$等价于$b$。

3.2 对数

$$\log_b{a^n}=n\log_b{a}$$

3.3 阶乘

$$\lg(n!)=\Theta(n\lg{n})$$

通过极限确定渐近符号

$$\lim_{n\rightarrow+\infty} \frac{f(n)}{g(n)} = \lambda > 0 \Longleftrightarrow f(n)=\Theta(g(n))$$

4 强弱关系 —— 强吃弱

大$O$记号从弱到强依次为:
$$O(1),O(\log{n}),O(n),O(n\log{n}),O(n^2),O(n^3),O(2^n)
$$
这些大$O$记号在做加法时满足强吃弱,例如
$$3n+1=O(n)\\
2n^2+3n+1=2n^2+O(n)=O(n^2)+O(n)=O(n^2)$$


最初的梦想 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:函数的增长
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址