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)

常用数据结构

image

数据结构分类

分类

数据结构比较

数据结构比较

O符号

  1. O(1):最低的复杂度,无论数据量大小,耗时都不变,都可以在一次计算后获得。哈希算法就是典型的O(1)
  2. O(n):线性,n表示数据的量,当量增大,耗时也增大,常见有遍历算法
  3. O(n²):平方,表示耗时是n的平方倍,当看到循环嵌循环的时候,基本上这个算法就是平方级的,如:冒泡排序等
  4. O(log n):对数,通常ax=n,那么数x叫做以a为底n的对数,也就是x=logan,这里是a通常是2,如:数量增大8倍,耗时只增加了3倍,二分查找就是对数级的算法,每次剔除一半
  5. O(n log n):线性对数,就是n乘以log n,按照上面说的数据增大8倍,耗时就是8*3=24倍,归并排序就是线性对数级的算法
    image

数据结构选择

image

常用数据结构和算法的时间复杂度

image

image

image

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