时间复杂度计算

学习数据结构时，

觉得时间复杂度计算很复杂，

怎么也看不懂，

差不多三年之后，

还是不懂，马上就要找工作了，赶紧恶补一下吧：

首先了解一下几个概念。

一个是时间复杂度，

一个是渐近时间复杂度。

前者是某

个算法的时间耗费，

它是该算法所求解问题规模

n

的函数，

而后者是指当问题规

模趋向无穷大时，该算法时间复杂度的数量级。

当我们评价一个算法的时间性能时，

主要标准就是算法的渐近时间复杂度，

因此，

在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度

T(n)=O(f(n))

简称为时间复杂度，其中的

f(n)

一般是算法中频度最大的语句频度。

此外，

算法中语句的频度不仅与问题规模有关，

还与输入实例中各元素的取值相

关。

但是我们总是考虑在最坏的情况下的时间复杂度。

以保证算法的运行时间不

会比它更长。

常见的时间复杂度，

按数量级递增排列依次为：

常数阶

O(1)

、

对数阶

O(log2n)

、

线性阶

O(n)

、线性对数阶

O(nlog2n)

、平方阶

O(n^2)

、立方阶

O(n^3)

、

k

次方

阶

O(n^k)

、指数阶

O(2^n)

。

1. 

大

O

表示法

定义

设一个程序的时间复杂度用一个函数

 T(n) 

来表示，对于一个查找算法，如下：

int seqsearch( int a[], const int n, const int x)  

{  

int i = 0;  

for (; a[i] != x && i