美文网首页算法导论
《算法导论》渐近记号

《算法导论》渐近记号

作者: Sun东辉 | 来源:发表于2022-06-08 10:30 被阅读0次

    \Theta 记号

    定义

    对一个给定的函数 g(n),用 \Theta(g(n))来表示函数集合:\Theta(g(n)) = {f(n):存在正常量 c_1、c_2n_0使得对所有 n \geq n_0,有 0 \leq c_1g(n)\leq f(n)\leq c_2g(n)}。

    解释

    对任一个函数 f(n),若存在正常数 c_1c_2,使当 n 充分大时,f(n) 能被夹在 c_1g(n)c_2g(n)中间,则 f(n) 属于集合 \Theta(g(n))。因为 \Theta(g(n)) 是一个集合,可以写成 “f(n)\in\Theta(g(n))”,表示 f(n) 是 \Theta(g(n)) 的元素。不过,通常写成 “f(n)=\Theta(g(n))”来表示相同的意思。

    上图给出函数 f(n) 与 g(n) 的直观图示,其中 f(n) = \Theta(g(n))。对于所有位于 n_0 右边的 n 值,f(n) 的值落在 c_1g(n)c_2g(n) 之间,换句话说,对所有的 n≥n_0,f(n) 在一个常因子范围内与 g(n) 相等。我们说 g(n) 是 f(n) 的一个渐近确界。

    \Theta(g(n)) 的定义需要每个成员 f(n)\in\Theta(g(n))都是渐近非负,也就是说当 n 足够大时 f(n) 是非负值(渐近正函数则是当 n 足够大时总为正值)。这就要求函数 g(n) 本身也必须是渐近非负的,否则集合 \Theta(g(n)) 就是空集。因此,假定 \Theta 记号中用到的每个函数都是渐近非负的。

    例子:

    例 1:证明 \frac{1}{2}n^2-3n=\Theta(n^2)

    首先要确定常数 c_1c_2n_0,使得对所有的 n≥n_0,即

    c_1n^2\leq\frac12n^2-3n\leq c_2n^2

    成立,用 n^2 除不等式得

    c_1\leq\frac12-\frac3n\leq c_2

    右边的不等式在 c_2\geq\frac{1}{2} 时对所有的 n\geq1 成立。同样,左边的不等式可以让 c_1\leq\frac{1}{14} 时对所有的 n\geq7 成立。这样,通过选择 c_1=\frac{1}{14}c_2=\frac{1}{2},以及 n_0=7,可以证明 \frac{1}{2}n^2-3n=\Theta(n^2)。当然,还存在其他的常数选择,而重要的是确实存在某个选择。需要注意的是,这些常数依赖于函数 \frac{1}{2}n^2-3n\Theta(n^2)中不同的函数通常需要不同的常数。

    例 2: 证明 6n^2\Theta(n^2)

    使用反证法进行证明,假设存在常数 c_2n_0,使对所有的 n\geq n_0,有 6n^3\leq c_2n^2;这样就有 n\leq \frac{c_2}{6},这对于任意大的 n 是不可能成立的,因为 c_2 是常数。

    例 3: 任意的二次函数 f(n)=an^2+bn+c,其中 a,b 和 c 都是常数,且 a > 0

    舍掉低阶项并忽略常数项得出 f(n)=\Theta(n^2)。可以发现,当常数 c_1=\frac{a}{4}c_2=\frac{7a}{4}n_0=a\times max(\frac{\vert b\vert}a,\sqrt{\frac{\vert c\vert}a}),时,对于所有的 n\geq n_0,满足 0\leq c_1n^2 \leq an^2+bn+c \leq c_2n^2

    O 记号

    定义:

    \Theta 记号渐近地给出了一个函数的上界和下界。当只有一个渐近上界时,使用 O 记号。对于给定函数 g(n),用 O(g(n))(读作“大 Og(n)”,有时仅读作”Og(n)”)来表示以下函数的集合:O(g(n))={f(n): 存在正常量 c 和 n_0,使得对所有 n≥n_0,有 0≤f(n)≤cg(n)}

    解释

    上图说明了 O 记号的直观意义,对位于 n_0 右边的 n 值,函数 f(n) 的值在 g(n) 之下。
    利用 O 记号,我们常常能通过查看算法的总体结构来描述算法的运行时间。例如,插入排序算法中的二重循环结构立即能引出其最坏情况运行的上界 O(n^2),内循环每一轮迭代的代价以 O(n^0)(常量 O(1))为上界,下标 i 和 j 最大可以取到 n,对于 n^2 个 i 值和 j 值对中的每一对,内循环至多执行一次。

    \Omega 记号

    定义

    正如 O 记号提供了一个函数的渐近上界,\Omega 记号提供了渐近下界。对于给定的函数 g(n),用 \Omega(g(n))(读作“大 \Omega g(n)”,有时仅读作“\Omega g(n)”)来表示以下函数的集合:\Omega g(n) = {f(n):存在正常量 c 和 n_0,使得对所有 n≥n_0,有 0≤cg(n)≤f(n)}

    解释


    上图说明了 \Omega 记号的直观意义,对所有在 n_0 右边的 n 值,函数 f(n) 的数值等于或大于 cg(n)。

    o 记号

    O 记号与 o 记号的定义是类似的,主要区别在于对 f(n)=O(g(n)),界 0≤ f(n)≤ cg(n) 对某个常数 c>0 成立,但对 f(n)=o(g(n)),界 0≤ f(n)≤ cg(n) 对所有常数 c>0 成立。从直觉上看,在 o 表示中当 n 趋于无穷时,函数 f(n) 相对于 g(n) 来说就不重要了,即
    \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}\;=\;0

    \omega 记号

    定义

    表示非渐近紧确的下界,它的一种定义为 f(n)\in \omega(g(n)),当且仅当 g(n)\in o(f(n))\omega(g(n)) 的形式定义为集合 \omega(g(n))=f(n),对任意正常数 c>0,存在常数 n_0>0,有 0\leq cg(n)<f(n)
    例如:\frac{n^2}{2}=\omega(n),但 \frac{n^2}{2}\omega(n^2)。关系 f(n)=\omega(g(n)) 意味着
    \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}\;=\;\infty
    如何这个极限存在。也就是说当 n 趋于无穷时,f(n) 相对 g(n) 来说变得任意大了。

    一个例子

    p(n)=\sum_{i=0}^da_in^i 为一个 n 的 d 次多项式,其中 a_d > 0,令 k 为一个常数。利用渐近记号的定义来证明如下性质:
    1. 若 k≥d,则 p(n)=O(n^k)
    2. 若 k≤d,则 p(n)=\Omega(n^k)
    3. 若 k=d,则 p(n)=\Theta(n^k)
    4. 若 k>d,则 p(n)=o(n^k)
    5. 若 k<d,则 p(n)=\omega(n^k)

    解:该公式可以改写为:

    p(n)=\sum_{i=0}^da_in^i = a_dn^d+a_{d-1}n^{d-1}+...+a_1n+a_0

    对于性质 1

    cn^d\geq a_dn^d+a_dn^{d-1}+...+a_1n+a_0

    使

    c=a_d+b

    得到

    a_d+b \geq a_d+\frac{a_{d-1}}{n}+\frac{a_{d-2}}{n^2}+\frac{a_0}{n^d}

    进一步化简得到

    b \geq \frac{a_d-1}{n}+\frac{a_d-2}{n^2}+...\frac{a_0}{n^d}

    使 b= 1,则

    n_0=\max(da_{d-1},d\sqrt{a_d-2},...,d\sqrt[d]{a_0})

    此时对于 n>n_0时,p(n)\leq cn^d\;,性质 1 得到证明。
    同理,当 b=-1 时,可以证明性质 2 。
    其余性质的证明方式类似。

    相关文章

      网友评论

        本文标题:《算法导论》渐近记号

        本文链接:https://www.haomeiwen.com/subject/hdvemrtx.html