常见时间复杂度

一般有以下几种：O(1), O(logn),  O(n),  O(nlogn),  O(n^2),..........

 1、O(1)：只有有限的语句，没有循环

 2、O(logn)：一层循环，但每次减半(减1/2、1/3等等，情况类似)，如二分查找等算法

for(int i =0; i

{

i+=1;

}//此循环不是步进1，而是步进2，所以假设x次循环完，则2^x=n，即x=log2n(2为底)

 3、O(n)：一层循环，n次

int k；

for(int i =0; i

{

k+=i;

}

 4、O(nlogn)：两层循环，一层普通的n次，一层每次减半

int k；

for(int i =0; i

{

k+=i;

for(int j =0; j

{

i+=1;

}

}

 5、O(n^2)：两层普通循环，每层n次(跟n相关，不一定等于n)

阅读(835) | 评论(0) | 转发(0) |

0

上一篇：虚函数与纯虚函数

下一篇：auto extern static const

给主人留下些什么吧！~~

评论热议

请登录后评论。

登录 注册