现在的位置: 首页 > 综合 > 正文

算法分析时间复杂度

2017年10月14日 ⁄ 综合 ⁄ 共 415字 ⁄ 字号 评论关闭

对一个算法的分析,很多时候我们更关心算法运行的时间复杂度。算法的时间复杂度中,我们关心算法运行的时间上界。即大O阶分析方法。

时间复杂度的分类:

1、没有循环递归的基本都是常数阶。

2、有一层循环的就是线性阶。

for(int i=0;i<n;i++){

//dosth

}

3、对数阶:一般类似如下:

while(i<n){

i=i*2;

}

会循环log2N次。所以是对数阶。


4、平方阶

4.1有两个for循环如下所示:

for(int i=0;i<n;i++)

for(int j=0;j<n;j++){

//执行O(1)的操作

}

4.2有两个for循环如下所示:

for(int i=0;i<m;i++)

for(int j=0;j<n;j++){

//执行O(1)的操作

}

4.3有两个for循环如下所示:

for(int i=0;i<m;i++)

for(int j=0;j<i;j++){

//执行O(1)的操作

}


一个算法的时间复杂度,可以求各个关键步骤的累加和。主要是循环。




抱歉!评论已关闭.