究竟什么是时间复杂度，怎么求时间复杂度，看这一篇就够了

时间复杂度就是用来方便开发者估算出程序的运行时间

我们该如何估计程序运行时间呢，我们通常会估计算法的 *** 作单元数量，来代表程序消耗的时间， 这里我们默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么 *** 作单元数量便用函数f(n)来表示

随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))

这里就要说一下这个大O，什么是大O呢，很多同学说时间复杂度的时候都知道O(n)，O(n^2)，但说不清什么是大O

算法导论给出的解释： 大O用来表示上界的 ，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是O(n^2)

但是在数据本来有序的情况下时间复杂度是O(n)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)

同样的同理我们在看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)

但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一宏饥旅个默认规定，我们这里说的O 代表的就是一般情况，不是严格的上界

所以这里大家知道这么一回事就好了

面试中面试官绝对不会针对快速排序的时间复杂度问题来讨论O的定义， 大家知道讨论的时间复杂度就是指一般情况下的时间复杂度就好了。

大家要对算法的时间复杂度有这样的一个概念

就是同一个算法的时间复杂度不是一成不变的，和输入的数据形式依然有关系

我们主要关心的还是一般情况下的数据形式 。

面试中说道算法的时间复杂度是多少指的都是一般情况

但是如果面试官和我们深入探讨一个算法的实现以及性能的时候 我们就要时刻想着 数据用例的不一样 时间复杂度也是不同的，这一点同学们要注意

这个图中我们可以看出 不同算法的时间复杂度 在不同数据输入规模下的差异 。

我们在决定使用那些算法的时候 ，不是时间复杂越低的越好，要考虑数据规模，如果数据规模很小 甚至可以用O(n^2)的算法比 O(n)的更合适

就像上图中图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的，所花费的时间也是最少的。

那我们为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度

而且要默认O(n) 优于O(n^2) 呢 ？

这里就又涉及到大O的定义

因为 大O其实就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度 ，这个点也就是 常数项系数已经不起决定性作用的点。

例如上图中 20 就是那个点 ，n只要大于20 常数项系数已经不起决定性作用了。

所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下我们都是默认数据规模足够的大，基于这样的事实 我们给出的算法时间复杂的的一个排行如下所示：

O(1)常数阶 <O(logn)对数阶 <O(n)线性阶 <O(n^2)平方阶 <O(n^3)(立方阶) <O(2^n) (指数阶)

我们平时说这个 算法的时间复杂度是logn的，一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

为什么可以这么做呢？

如下图所示

假如我们有两肢凯个算法的时间复杂度 分别是log以2为底n的对数 和 log 以10为底n的对数

那么这里如果大家还记得我们高中数学的话， 应该不能理解 以2为蔽凳底n的对数 = 以2为底10的对数 乘以 以10为底n的对数

那这里以2为底10的对数 是一个常数，而我在上面已经讲述了我们计算时间复杂度是忽略常数项系数的

抽象一下 log 以i为底n的对数 等于 log 以j为底n的对数，所以我们忽略了i，直接说是logn，正式因为logij 是就一个常数

所以，这样就应该不难理解了 我们为什么忽略底数了

有时候，我们去计算时间复杂度的时候 发现不是一个 简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，例如：

O(2*n^2 + 10*n + 1000)

那这里我们通常如何描述这个算法的时间复杂度呢，一种方法就是简化法

去掉运行时间中的加法常数项 （因为常数项并不会因为n的增大而增加计算机的 *** 作次数）

O(2*n^2 + 10*n)

去掉常数系数 （我们刚刚已经详细讲过为什么可以去掉常数项的原因了）

O(n^2 + n)

只保留保留最高项 去掉数量级小一级的n （因为n^2 的数据规模远大于 n），最终简化为：

O(n^2)

如果这一步同学们理解有困难，那也可以做提取n的 *** 作，变成 O(n(n+1)) ，省略加法常数项后 也别变成了

O(n^2)

所以最后我们说：我们这个算法的算法时间复杂度是 O(n^2)

也可以用另一种简化的思路，当n大于40的时候 ， 这个复杂度 会一直小于 O(3*n^2)

O(2*n^2 + 10*n + 1000) <O(3*n^2)

所以说 最后我们省略掉常数项系数最终时间复杂度也是 O(n^2)

我们通过一道题目，来看一下具体时间复杂度应该怎么算

题目描述：找出n个字符串中相同的两个字符串（假设这里只有两个相同的字符串）

一些同学可能以为解决这道题目可以采用枚举遍历的解法，时间复杂度是 O(n^2)

这个时间复杂度其实是不对的。

这里 一些同学忽略了字符串比较的时间消耗，这里并不像int 型数字做比较那么简单

除了n^2 次的遍历次数外， 字符串比较依然要消耗m次 *** 作（m也就是字母串的长度），所以时间复杂度是 O(m*n*n)

那么我们再想一下其他解题思路

我们先排对n个字符串按字典序来排序，排序后n个字符串就是有序的，意味着两个相同的字符串就是挨在一起

然后在遍历一遍n个字符串，这样就找到两个相同的字符串了

那我们来看看这种算法的时间复杂度

快速排序时间复杂度 为O(nlogn)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有m次的字符比较的 *** 作，就是 O(m*n*logn)

之后我们还要遍历一遍这n个字符串找出两个相同的字符串，别忘了遍历的时候依然要比较字符串，所以总共的时间复杂度是 O(m*n*logn + n*m)

我们对 O(m*n*logn + n*m) 进行简化 *** 作，把 m*n 提取出来变成 O(m*n*(logn + 1)) ，

在省略常数项最后的时间复杂度是 O(m*n*logn) ， 那我们比较一下时间效率 O(m*n*logn) 是不是比第一种方法 O(m*n*n) 更快一些呢

很明显 O(m*n*logn) 要优于 O(m*n*n)

所以 先把字符串集合排序在遍历一遍找到两个相同字符串的方式要比直接暴力枚举的方式更快 。

通过这个例子 希望大家对时间复杂的是怎么算的有一个初步的理解和认识。

这东西详细手打有点，去帮你找了个讲的比较详细的。

哪不懂可以追问

简单理解，时间复杂度就是执行语句被调用了多少次。

(1)如果只调用了一次，如：

x=5

if(x<-4)

{x=x+4}

else

{x=x+3}

在大括号中的内容，只会调用一个语句，那么O(n)=1

(2)如果调用了两次，如：

x=5

if(x<-4)

{x=x+4}

else

{x=x+3}

x=x+56

在大括号中的内容，只会调用一个语句，但是在最后，还有一个计算公式要调用语句；码滚总共加起来就是调用2次。那么O(n)=2

（3）用1个FOR循环调用

for(x=0x<nx++)

{x=x+1}

x会从0到n-1循环，执行的语句就是将当前x值加入新的x中，总共调用n次；那么O(n)=n

(4）用2个嵌套FOR循环嫌升调用

for(x=0x<nx++)

{

for(y=1y<=ny++)

{x=x+y}

}

遇到嵌套循环，可以先将外面的FOR语句中的变量固定为初始值x=0，主要看里面迟者余的FOR语句的时间复杂度，很明显，里面语句执行次数是从1到n总共调用n次，O(n)=n；这还只是x=0时的调用。x可以从0到n-1，共n次。每次调用都会执行n次调用y的情况，因此，执行语句x=x+y；总共会调用n*n次。O(n)=n^2。

数执行语句的执行次数，就是时间复杂度。注意：

(1)找到正确的执行语句。

(2)for循环中的初始值和终止值。

for(i=0i<ni++)

i值变化是从0到n-1，共n次。

for(i=0i<=ni++)

i值变化是从0到n，共n+1次。

(3)注意for循环的调用顺序，从里面到外面进行的。

算法复杂度的介绍，见百科：

http://baike.baidu.com/view/7527.htm

时间复杂度

时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

计算方法

1. 一般情况下，算法的基本 *** 作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））

分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。

2. 在计算时间复杂度的时候，先找出算法的基本 *** 作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数谨空量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））

例：算法：

for（i=1i<=n++i）

{

for(j=1j<=n++j)

{

c[ i ][ j ]=0//该步骤属于基本 *** 作 ，执行次数：n的平方 次

for(k=1k<=n++k)

c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]//该步骤属于基本 *** 作 ，执行次数：n的三次方 次

}

}

则有 T（n）= n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级

则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c

则该算法的 时间复杂度：T（n）=O（n^3） 注：n^3即是n的3次方。

3.在pascal中比较容易理解，容易计算的方法是：稿晌缓看看有几重for循环，只有一重则时间复杂度为O（n）,二重则为O（n^2），依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。

分类

按数量级递增排列，常见的时间复杂度有：

常数阶O(1),对数阶O(log2n),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，

k次方阶O(n^k), 指数阶O(2^n) 。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

关于对其的理解

《数据结构（C语言版）》------严蔚敏 吴伟民编著 第15页有句话"整个算法的执行时间与基本 *** 作重复执行的次数成正比。"

基本 *** 作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O( f(n) )

如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间。

而该页对“语句频度”也有定义：指的是该语句重复执行的次数。

如果是基本 *** 作所在语句重复执行的次数，那么就该是f(n)。

上边的n都表示的问题规模。

以下来自百度知道：

对于这些算法

(1) for(i=1i<=ni++)

for(j=1j<=nj++)

s++

(2) for(i=1i<=ni++)

for(j=ij<=nj++)

s++

(3) for(i=1i<=ni++)

for(j=1j<=ij++)

s++

(4) i=1k=0

while(i<=n-1){

k+=10*i

i++

}

(5) for(i=1i<=ni++)

for(j=1j<=ij++)

for(k=1k<=jk++)

x=x+1

对应的时间复杂度为：

1.时间复杂度O(n^2)

2.时间复杂度O(n^2)

3.时间复杂度O(n^2)

4.时间复杂度O(n)

5.时间复杂度O(n^3)

一般来说，时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)

比如：一般总运算次数表达式类似于这样：

a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f

a<>0时，时间复杂度就键模是O(2^n)

a=0,b<>0 =>O(n^3)

a,b=0,c<>0 =>O(n^2)依此类推

那么，总运算次数又是如何计算出的呢？

一般来说，我们经常使用for循环，就像刚才五个题，我们就以它们为例

1.循环了n*n次，当然是O(n^2)

2.循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)

3.循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)

4.循环了n-1≈n次，所以是O(n)

5.循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3，不考虑系数，自然是O(n^3)

另外，在时间复杂度中，log(2,n)(以2为底)与lg(n)(以10为底)是等价的，因为对数换底公式：

log(a,b)=log(c,b)/log(c,a)

所以，log(2,n)=log(2,10)*lg(n),忽略掉系数，二者当然是等价的

---