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

目录

2.1.概述

2.2.时间复杂度的计算

2.2.1.渐进复杂度

2.2.2.渐进上界

2.2.3.渐进下届

2.2.4.复杂度排序

2.2.5.举几个例子

---

2.1.概述

算法的基本定义：

求解问题的一系列计算或者操作。

衡量算法性能的指标：

• 时间复杂性
• 空间复杂性

这两个指标里最有用的是时间复杂度，平时谈的算法复杂度一般指的就是时间复杂度。

空间复杂性：

算法执行所用的空间。

时间复杂性：

用time的缩写T表示算法执行所需要的时间，这里的时间指的不是传统意义上时分秒的时间，而是将一步操作抽象成一个单位时间，所以算法的时间复杂度里的时间可以理解为所要执行的步骤的数量，即操作次数。

时间复杂性分为，最好时间复杂性、最坏时间复杂性、平均时间复杂性。这里面最有用的指标是最坏时间复杂性，它标识了一个算法执行的最差效率，要是它是能接受的，那么这个算法的执行效率就不用担心了。

2.2.时间复杂度的计算

2.2.1.渐进复杂度

时间复杂度是随输入规模变化而变化的一个值，这种关系不难看出是一个函数关系，所以时间复杂度的计算其实就是推导出当前算法和输入规模之间的这个关系函数。这个关系函数可以是根据算法的具体步骤一步步相加最后推到出来的详细的一个函数表达式，但是其实我们知道时间复杂度函数一定是一个自变量为输入规模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++;
    }
}