首页 > 代码库 > 对时间复杂度的简单理解

对时间复杂度的简单理解

时间复杂度:计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间(百度)。时间复杂度常用来估算一个程序在n为一定值的时候需要的时间,来判断你的算法是否高效。

通常时间复杂度和渐进时间复杂度不做区分。下面给例题。

1:a=b;b=c;a=c;

T(n)=1。

 

2:(1) x=0;y=0; 
(2) for(k-1;k<=n;k++) 
(3)      x++; 
(4) for(i=1;i<=n;i++) 
(5)        for(j=1;j<=n;j++) 
(6)          y++; 

对于存在多个循环的,找循环嵌套层数最多的作为计算依据。T(n)=n^2.

 

3:(1) x=1; 
(2) for(i=1;i<=n;i++) 
(3)        for(j=1;j<=i;j++) 
(4)            for(k=1;k<=j;k++) 
(5)                x++; 

T(n)=n^3。

小结:时间复杂度按数量级递增排列依次为:常数(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2^n)

 

假设时间限制为1s 

100W 游刃有余;

1000W 勉勉强强;

10000W 悬;

对时间复杂度的简单理解