logo头像

待到风起时,扬帆济沧海

算法笔记

算法推导大O阶方法

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中,只保留最高阶项
  3. 如果最高阶存在且不是1,则去除与这个项相乘的常数

常数阶

首先顺序结构的时间复杂度。下面这个算法案例:

1
2
3
int sum=0,n=100 /*执行第一次*/
sum=(1+n)*n/2 /*执行第一次*/
printf("%d",sum) /*执行第一次*/

这个算法的运行函数是f(n)=3,所以根据推倒大O,如果结果是常数3,所以常熟3改为1,记为O(1),事实上无论sum=(1+n)*n/2执行多少次时间都是恒定的。

线性阶

线性阶的循环结构会复制很多。要确定某个算法的阶次,我们常常需要确定某个特定语句或某个函数运行的次数。下面的代码示例复杂度为O(n),因为循环体中的代码要执行n次。

1
2
3
4
int i;
for(i=0;i<n;i++){
/*执行复杂度未O(1)的程序*/
}

对数阶

下面这段代码,由于每次count乘以2以后,就距离n更近,由$2^x=n 得到x=log2n。所以这个循环的负责度为O(logn).

1
2
3
4
5
int count=1;
while(count<n){
count=count*2
/*执行复杂度未O(1)的程序*/
}

平方阶

下面这段代码,是一个循环嵌套的,时间复杂度为O(n^2)

1
2
3
4
5
6
int i,j
for(i=0;i<n;i++){
for(j=0;j<n;j++){
/*执行复杂度未O(1)的程序*/
}
}

如果外循环改成了m,时间复杂度就是,时间复杂度为O(n*m)

1
2
3
4
5
6
int i,j
for(i=0;i<m;i++){
for(j=0;j<n;j++){
/*执行复杂度未O(1)的程序*/
}
}

所以总结规律,循环的时间复杂度等于循环体复杂度乘以改循环的运行的次数

1
2
3
4
5
6
int i,j;
for(i=0;i<m;i++){
for(j=i;j<n;j++){ //注意j=i
/*执行复杂度未O(1)的程序*/
}
}

由于i逐步递减,所以总执行次数为:n+(n-1)+(n-2)+…+1=n(n+1)/2=n^2/2+n/2
所以我们推倒方法,第一条,没有加常数不予考虑;第二条,只保留最高阶,因此保留n^2/2;第三条,去除这个项相乘的常数,也就是去除1/2,最终这段代码的复杂度未O(n^2)

评论系统未开启,无法评论!