数据结构绪论-时间复杂度和空间复杂度(上)-学习笔记-3

引入

前一讲,我们介绍了什么是算法的量度,以及如何用渐进函数来看哪些对算法的复杂度影响最大,今天我们就来看看如何计算复杂度。

时间复杂度

  • 定义:在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。所以,算法的时间复杂度,就是算法的时间量度:

    T(n)=O( f(n) )

  • 时间复杂度:它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同。称作算法的渐进时间复杂度,简称为时间复杂度。

    f(n) 是问题规模 n 的某个函数(上节我们研究过,能够改变结果的那个函数)

上面的定义很复杂,但只要记住,执行次数==时间就可以了。

  • 记作:我们用大写 O()来体现算法的时间复杂度的记法,我们称之为大 O 记法。

一般来说,随着输入规模 n 的增大,T(n)增长最慢的算法为最优算法,也就是说 n 从 0 提升到10000000,但是算法的解题次数并没有随之提升,或者只有缓慢提升,表示算法非常的优秀。

计算时间复杂度

我们知道了什么是时间复杂度,那么我们该如何推到处这个大 O 阶呢?

  • 加法常数:我们用常数 1 取代运行时间中的所有加法常数
  • 最高价:在修改后的运行次数函数中,只保留最高阶项
  • 去乘数常数:如果最高项存在,且不是1,则去除与这个最高项相乘的常数
  • 最后:剩下的数就是大 O 阶

几个例子

我们用上面计算大 O 阶的方法,来解以下几个例题

常数阶

求下列算法的时间复杂度

1
2
3
4
5
6
int sum=0,n=100;
printf("Bliner is a cooder\n");
printf("Bliner is a cooder\n");
printf("Bliner is a cooder\n");
printf("Bliner is a cooder\n");
sun=(1+n)*n/2;

如果你数了数,有6行代码
f(n)=1+1+1+1+1+1
就说结果是 O(6)那就错了!
因为我们用常数 1 取代运行时间中的所有加法常数`,所以,上面折麽多,我们将所有的都看做1,答案是O(1)。

sun=(1+n)*n/2;
这个也是一个普通项目,因为 cpu 只计算一次,所以这也是+1的常数项

线性阶

求下列算法的时间复杂度

1
2
3
4
int i,n=100,sun=0;
for (i=0;i<n;i++){
sum=sum+i;
}

非嵌套循环一般都涉及线性阶,线性阶就是随着问题 n 的规模扩大,对应的计算次数呈直线增长。

在这个题里面,n=100,执行100次。所以,上面的例子时间复杂度 O(n)。

平方阶

求下列算法的时间复杂度

1
2
3
4
5
6
int i,j,n=100,sun=0;
for (i=0;i<n;i++){
for (j=0;j<n;j++){
sum=sum+i;
}
}

这就是一个嵌套循环,也就是一个循环中包含另一个循环,那么实际执行下来,应该为100X100,也就是 $n^2$ ,所以这段代码的时间复杂度是$O(n^2)$。

如果,有三个嵌套循环呢?答案就是$O(n^3)$了!

所以,我们很容易得出,
循环的时间复杂度 == 循环体本身的复杂度 X 该循环题执行的次数

如果嵌套循环的循环次数不一致呢?

1
2
3
4
5
6
int i,j,n=100;
for(i=0;i<100;i++){
for(j=i;j<n;j++){
printf("Bliner'blog!\n");
}
}

我们看到

  • 外层循环0次,内层循环执行 n次
  • 外层循环1次,内层循环执行 n-1次
  • 外层循环2次,内层循环执行 n-2次

以此类推

其实这就是 n(n+1)/2 就是我们一开始那个求和公式。
$n(n+1)/2=n^2/2+n/2$
第一条,没有常数相加,不执行操作。
第二条,只保留最高项,所以 n/2 要去掉
第三条,1/2 乘以 $n^2$ ,n 的指数不为1,所以 1/2 要去掉
结果,$O(n^2)$

对数阶

求下列算法的时间复杂度

1
2
3
4
int i=1,n=100;
while(i<n){
i=i*2;
}

我们分析一下循环如何跳出,即

i=i*2 也就是 x 个 2相乘
$2^x=n$ 也就是 $x=log_{2}^{n}$

所以,时间复杂度位 O(Logn);

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!