时间复杂度

百度百科-时间复杂度

 

等差：

 

 

等比：

  

对数阶：

int count = 1;  
while （count < n）  
{  
	count = count * 2;  
} 

 

由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由2的X次方=n  ==》 x=log(2)n。所以这个循环的时间复杂度为O(logn)。

 

------------------------------------------------------------------------------------------------------------------------------------------------

算法复杂度分为时间复杂度和空间复杂度。

时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

 

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

  

 

分类

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

常数阶O(1) 

线性阶O(n)

 

对数阶O(log(2)n) 

线性对数阶O(nlog(2)n)

 

平方阶O(n^2)

立方阶O(n^3)

...

k次方阶O(n^k),

指数阶O(2^n) 

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

 

 

计算方法

 

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

 

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

 

2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级

（它的同数量级有以下：1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))

 

例子1：

for(i=1;i<=n;++i)
{
	for(j=1;j<=n;++j)
	{
		c[i][j]=0;//该步骤属于基本操作执行次数：n的平方次
		for(k=1;k<=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次方。

 

 1.

for i:=1 to 100 

      do for j:=1 to 100 

             do s[i,j]:=0;

执行次数100*100次，时间复杂度O(1)

 

//O(10000)和O(1)都是常数阶，所以O(10000)可以近似看成O(1)。

 

2.

for i:=1 to n 

      do for j:=1 to 200 

            do s[i,j]:=0;

执行次数n*200次，时间复杂度O(n)

 

3.

for i:=1 to n 

        do for j:=1 to n div 2 

              do s[i,j]:=0;

执行次数n*n/2次，时间复杂度O(n^2)

 

//O(n*n/2)和O(n^2)都是平方阶，所以O(n*n/2)可以近似看成O(n^2)

 

4.

for i:=1 to n

     do for j:=1 to n-1 

           do for k:=1 to n-2 

                 do s[i,j,k]:=0;

执行次数n*(n-1)*(n-2)次，时间复杂度O(n^3)

 

5.

for i:=1 to n do

   begin

         for j:=1 to n 

                 do s[i,j,0]:=0;

         for j:=1 to n 

                 do for k:=1 to n do s[i,j,k]:=1;

  end;

执行次数n*(n+n*n)次，时间复杂度O(n^3)

 

 

一个算法在计算机上的执行效率，主要看这个算法的时间复杂度是属于哪一阶的，常数的影响并不大。当n非常大时，O(10000)的算法和O(1)的算法执行的时间差不多，O(n*n/2)的算法和O(n^2)的算法执行的时间差不多，但是O(n*n/2)的算法会比O(10000)的算法慢很多。

 

 

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

 

问题1：

冒泡排序在最坏的情况下的比较次数是O(N^2) 

怎么有的就写冒泡排序在最坏情况下的比较次数是n(n-1)/2

 

一头雾水

 

答：

冒泡排序是一种用时间换空间的排序方法，最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列，第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4，4比5小，交换位置变成4 5 3 2 1；比较5和3，3比5小，交换位置变成4 3 5 2 1……最后比较5和1，1比5小，交换位置变成4 3 2 1 5。这时候共进行了4次比较交换运算，最后1个数变成了数列最大数。

第二次大循环从第一个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。

……

所以总的比较次数为 4 + 3 + 2 + 1 = 10次

对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数

 

而O(N^2)表示的是复杂度的数量级。举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相对10^8来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N^2。用O(N^2)就表示了其数量级（忽略前面系数0.5）。