您当前的位置: > 学院设备 >

算法剖析之日用标记父亲O、小o、父亲Ω标记、父

作者:admin 来源:未知 发布日期:2018-10-30

  父亲O标记(英语:Big O notation),又称为浸进标记,是用于描绘函数浸近行为的数学标记。更确切地说,它是用另壹个(畅通日更骈杂的)函数到来描绘壹个函数数级的浸近上界。在数学中,它普畅通用到来描写被截断的无量级数更是浸近级数的剩项;在计算机迷信中,它在剖析算法骈杂性的方面什分拥有用。

  1、O(1) 为日数级的时间骈杂度,算法是什分好。

  2、O(log n) 为对数级的时间骈杂度,算法也不错。

  3、O(n) 为线性级的时间骈杂度,算法也还行。

  4、O(nlog n)线性对数级的时间骈杂度,算法也还却以。

  5、O(n^2) 二次方级的时间骈杂度,算法拥有点差。

  6、O(n^3)叁次方级的时间骈杂度,算法差。

  7、O(2^n) 指数级的时间骈杂度,算法很差。

  8、O(n!)阶迨级的时间骈杂度,算法极差。

  父亲O正确到来说, 运用另壹个函数到来描绘壹个函数数级的**。

  小o呢则体即兴壹个函数浸进地小于另壹个函数,没拥有拥有等于。

  父亲Ω标记的定义与父亲O标记的定义相像,但首要区佩是,父亲O标记体即兴函数在增长到壹定程度时尽小于壹个特定函数的日数倍,父亲Ω标记则体即兴尽父亲于。父亲Ω标记首要是用到来描绘壹个函数数级的**。

  父亲Θ标记是父亲O标记和父亲Ω标记的结合。即: {!若 {\displaystyle {\begin{cases}f(\nu )=\mathrm {O} [g(\nu )]\f(\nu )=\Omega [g(\nu )]\end{cases}}} {\begin{cases}f(\nu )=\mathrm{O} [g(\nu )]\f(\nu )=\Omega [g(\nu )]\end{cases}}。

  此雕刻壹标记比值先由高道德纳于1970年提出产[1]。

  Θ标记既然是上界亦降谪人间相当于两者的结合,等于的意思。

  w标记体即兴降谪人间,父亲于的意思。

  函数f ( n )代表某壹算法在输入父亲小为n的情景下的工干量(效力),则在n趋势很父亲的时分,我们将f (n)与另壹行为已知的函数g(n)终止比较:

  1、假设0,则称f (n)在数级上严峻小于g(n),记为f (n)=o( g(n))。

  2、假设,则称f (n)在数级上严峻父亲于g(n),记为f (n)=w( g(n))。

  3、假设c,此雕刻边c为匪0日数,则称f (n)在数级上等于g(n),即f (n)和g(n)是相畅通个数级的函数,记为:f (n)=Θ( g(n))。

  4、假设f (n)在数级上小于或等于g(n),则记为f (n)=O( g(n))。

  5、假设f(n)在数级上父亲于或等于g(n),则记为f (n)=Ω( g(n))。

  父亲O父亲Ω邑是存放在c,小o小w邑是关于恣意c

  尽结

  Θ等于的意思。

  Ο体即兴上界,小于等于的意思。

  ο体即兴上界,小于的意思。

Power by DedeCms
4008-888-888
知识改变命运,知识创造财富,科技是第一生产力!