算法分析时间复杂度

时间:2022-07-07 16:49:52

对一个算法的分析,很多时候我们更关心算法运行的时间复杂度。算法的时间复杂度中,我们关心算法运行的时间上界。即大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)的操作

}


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