数据结构(2)时间复杂度——渐进时间复杂度、渐进上界、渐进下界

时间复杂度是随输入规模变化而变化的一个值，这种关系不难看出是一个函数关系，所以时间复杂度的计算其实就是推导出当前算法和输入规模之间的这个关系函数。这个关系函数可以是根据算法的具体步骤一步步相加最后推到出来的详细的一个函数表达式，但是其实我们知道时间复杂度函数一定是一个自变量为输入规模n的单调递增的一元函数。这种单调递增函数当自变量趋近于无穷大（即+∞）时，函数表达式里的常数项和阶数不是最高的项对变化来说是可以忽略不记的，所以我们用渐进复杂度就可以表示当输入规模趋于无穷大时候的时间复杂度。

渐进复杂性是算法复杂度的一种简化表示，即算法的复杂度可以表示为当输入规模趋于+∞时，变化最快的部分。假设T(n)是算法的时间复杂度函数，t(n)是算法的渐进复杂度，可以得到以下等式：

以上等式之所以成立不难推出，因为t(n)是T(n)中变化最快的部分，T(n)减去变化快的部分与T(n)的比值必然是随着n趋近于∞的时候，趋近于0的。

2.2.2.渐进上界

渐进上界，即当前算法在输入规模趋近于+∞时，时间复杂度不会超过的一个函数值。用大O表示，这种表示是抽象的、简介的、只保留重点因素的，一般我们说算法复杂度说的就是大O表示的渐进时间复杂度的上界。

渐进上界的定义：

设f和g是定义为自然数集N上的函数，若存在正数c和n0，使得对一切n≥n0有：

0≤f(n)≤cg(n)

成立，则称f(n)的渐进上界是g(n)，记作：

f(n)=O(g(n))

2.2.3.渐进下届

下界，即当前算法在输入规模趋近于+∞时，前算法运行时间的下限，采用大Ω符号来表示。

渐进上界的定义：

设f和g是定义为自然数集N上的函数，若存在正数c和n0，使得对一切n≥n0有：

0≤cg(n)≤f(n)

成立，则称f(n)的渐进下界是Ω(n)，记作：

f(n)=Ω(g(n))

2.2.4.复杂度排序

算法的时间复杂度最后表示出来一定是一个自变量为输入规模n的一元函数，这个一元函数还一定是个基本初等函数，基本初等函数无非就六种，所谓的复杂度排序其实也就是六种基本初等函数在自变量趋近于无穷大时的变化率：

常数级、对数级、线性级、多项式级是能接受的范围，

指数级、阶乘级是灾难性的。

2.2.5.举几个例子

O(N)的时间复杂度：

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

O(logN)的时间复杂度：

int i = 1;
while(i<n)
{
    i = i * 2;
}

O(n²) 的时间复杂度：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

算法