美文网首页
函数的渐近的界&阶的比较

函数的渐近的界&阶的比较

作者: 楠子小先生 | 来源:发表于2019-03-13 22:22 被阅读0次

一、函数的渐近的界

  我们在研究算法性能的时候,往往会在意算法的运行时间,而运行时间又与算法输入的规模相关,对于一个算法,我们可以求出运行时间和输入规模的函数,当输入规模足够大时,站在极限的角度看,就可以求出运行时间如何随着输入规模的无限增长而增长。
  这种令输入规模无限大 而研究运行时间增长情况的做法,就是在研究算法的渐近效率。

几种符号的直观理解:
Θ,O,Ω的图像表示

Θ(渐近紧确界):若 f ( n ) = Θ ( g ( n )),则存在 c1>0 ,c2 >0,s.t. n→∞时, f ( n )夹在 c1 g ( n )和 c2 g ( n )之间。即g(n)既是f(n)的渐近上界又是渐近下界,可假装理解为”f(n) = g(n)“
且当 f ( n ) = Θ ( g ( n ))时,有:

O (渐近上界):若f ( n ) = O ( g ( n )),则存在c>0, s.t. n→∞时,f(n)在cg(n)下面。即g(n)是f(n)的渐近上界,可假装理解为“f(n) <= g(n)”
o (非渐近紧确上界):与O的区别是,任意c>0, 都使f(n)在cg(n)下面。是非紧的上界,可假装理解为“f(n) < g(n)”
且当f ( n ) = o ( g ( n ))时,有:

Ω (渐近上界):若f ( n ) = Ω ( g ( n )),则存在c>0, s.t. n→∞时,f(n)在cg(n)上面。即g(n)是f(n)的渐近下界,可假装理解为“f(n) >= g(n)”
ω (非渐近紧确下界):与Ω的区别是,任意c>0, 都使f(n)在cg(n)上面。是非紧的下界,可假装理解为“f(n) > g(n)”
且当f ( n ) = ω ( g ( n ))时,有:

二、几个重要结论(阶的比较)

基本函数类:

至少指数级:2^n,3^n,n!,...
多项式级:n,n^2,nlogn,n^{1\over2},...
对数多项式级:logn,log^2n,loglogn,...
多项式函数<指数函数: n^d = o(r^n),r>1,d>0
对数函数<幂函数: ln n = o(n^d),d>0

对数函数:

(1)log_2n=Θ(log_tn)(换底)
(2)log_bn=o(n^α) (α>0)
(3)a^{log_bn}=n^{lob_ba}(即,形如指数函数的幂是log级,则可化成多项式级)

指数函数与阶乘:

Stirling公式: n!=\sqrt{2πn}({n\over e})^n(1+Θ({1\over n}))
n!=o(n^n)
n!=ω(2^n)
log(n!)=Θ(nlogn)

相关文章

  • 函数的渐近的界&阶的比较

    一、函数的渐近的界   我们在研究算法性能的时候,往往会在意算法的运行时间,而运行时间又与算法输入的规模相关,对于...

  • Asymptotic bounds of functions a

    函数的渐近的界 大符号 例子 大符号 例子 小符号 例子 小符号 例子 符号 有关函数渐近的界的定理 定理一 例子...

  • 二、函数渐近界的定理

    定理1: 设f和g是定义域为自然数集合的函数,(计算极限来确定阶) (1)如果lim f(n)/g(n)存在,并且...

  • 有关函数渐近的界的定理

    定理1 定理 设 f 和 g是定义域为自然数集合的函数. (1)如果 存在, 并且等于某个常数c>0, 那么 f(...

  • 算法(2)

    上篇算法(1) 一、函数的渐近增长 函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N, 使得对于...

  • 高等数学公式1

    反函数的导数等于直接函数导数的倒数! 和的N阶导数比较简单 微分和导数的公式

  • 三次样条曲线

    与多项式拟合比较,样条函数可以保证穿过所有点,样条函数是多项式的分段函数,同时保证点之间平滑过渡,一阶导数/二阶导...

  • 算法导论第3章 - 函数的增长

    渐近记号 渐近紧界既有渐近上界,又有渐近下界Θ(g(n))={ f(n):存在正常数c1,c2和n0,使对所有的n...

  • ζ坊‖6月 浮潮錾堑角国率

    阶界纵横

  • 算法和数据结构

    算法和数据结构 [TOC] 算法 函数的增长 渐近记号 用来描述算法渐近运行时间的记号,根据定义域为自然数集$N=...

网友评论

      本文标题:函数的渐近的界&阶的比较

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