数据结构时间复杂度讲解与练习

一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但是有时候，我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

    一般情况下，算法中基本操作重复执行的次数，是问题规模 n 的某个函数，用T(n)表示。若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度。

    时间频度不相同时，渐进时间复杂度Ｏ(f(n)) 有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。

现在我们根据一些书本上和网络上对时间复杂度概念的描述进行一下总结：

    T(n)，语句频度，时间频度，亦称为时间复杂度。

    O(f(n))，渐进时间复杂度。

前者T(n)是某个算法的时间耗费，它是该算法所求解 问题规模 n的函数，而后者O(f(n))是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度O(f(n))，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

注意：算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。

常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)或O(lbn)、线性阶O(n)、线性对数阶O(n*log2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。

·      下面有一道题目是可以帮助同学们理解概念的：

1、设三个函数f,g,h分别为 f(n)=100*n^3+n^2+1000 , g(n)=25*n^3+5000*n^2 , h(n)=n^1.5+5000*n*lgn

请判断下列关系是否成立：

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

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

(3) h(n)=O(n^1.5)

(4) h(n)=O(nlgn)

这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是 "若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C*f(n)。"（即书本中的定义）。通俗一点就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。

◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。

◆ (2)成立。与上同理。

◆ (3)成立。与上同理。

◆ (4)不成立。由于当n→∞时n^1.5比n*lgn递增的快，所以h(n)与nlgn的比值不是常数，故不成立。

理解完概念之后，就开始求算法的时间复杂度。

从概念中我们知道，要求时间复杂度O(f(n))，就必须要知道算法中频度最大的语句频度f(n)，那么要求最大的语句频度f(n)就必须要知道算法的语句频度T(n)。一般总的思路就是：T(n)->f(n)->O(f(n))。有时候可以直接找到算法中频度最大的语句，直接算出f(n)，然后写出O(f(n))。也有例外情况就是很难求出语句频度T(n)的

下面会用一些例子做详细的说明：O(1)

例1：Temp=i;i=j;j=temp;                    

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

例2：x=91; y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

else x++;

解答： T(n)=O(1)， 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。

O(n)     

例1：

i=1; k=0

while(i