怎么理解算法的时间复杂度

  • 2020 年 05 月 13 日
  • 228
  • 1070 字
  • 暂无评论

最近在自学数据结构,话说还是比较有难度的。也许我太垃圾了

就当水文简单科普科普吧,dalao们直接略过,哈哈哈。

引入概念

算法的时间复杂度,是衡量算法之间执行效率的一种标准。假设对于任何定义的问题,可以有N个解决方案。如果我有问题,并且与所有朋友讨论该问题,他们都会为我提供不同的解决方案。我可以根据情况决定哪种解决方案最好。

类似地,对于必须使用程序解决的任何问题,可以有无数个解决方案。让我们举一个简单的例子来理解这一点。下面我们有两种不同的算法来找到一个数字的平方:

第一种方案,解决这个问题可以运行一个for循环,从1开始循环n次,每次加n,合起来就是n的平方

//we have to calculate the square of n
for i=1 to n
    do n = n + n
// when the loop ends n will hold its square
return n

或者,我们可以简单地使用数学运算符*来进行计算。

//we have to calculate the square of n
return n*n

在以上两种简单算法中,我们可以看到单个问题如何具有许多解决方案。第一种解决方案要求循环执行 n 多次,而第二种解决方案使用数学运算符 * 将结果返回一行。那么哪一种是更好的方法,当然是第二种。

什么是时间复杂度?

算法的时间复杂度表示程序运行直至完成所需的总时间。

算法的时间复杂度通常使用 大O表示法表示 。 它是表示时间复杂度的一种渐进符号。 我们将在下一个教程中详细研究它。

时间复杂度通常是通过计算任何算法完成执行的基本步骤的数量来估算的。 像上面的示例一样,对于第一个代码,循环将运行 n 多次,因此时间复杂度将达到 n 最小,并且随着值的 n 增加,花费的时间也将增加。 对于第二个代码,时间复杂度是恒定的,因为它永远不会取决于的值 n ,它将始终以1步给出结果。

而且由于算法的性能可能随输入数据的不同类型而变化,因此对于一种算法,我们通常使用 最坏情况下的时间复杂度 ,因为这是任何大小的输入所花费的最大时间,这样才有参考意义。

时间复杂度的表示

这里举3个例子说明:

a) ++x; s=0;
b) for (int i=1; i<=n; i++) { ++x; s+=x; }
c) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }

对于上边的例子而言,a 的时间复杂度为$O(1)$,b 的时间复杂度为$O(n)$,c 的时间复杂度为为$O(n^2)$。

如果a、b、c组成一段程序,那么算法的时间复杂度为 $O(n^2+n+1)$。但这么表示是不对的,还需要对$n^2+n+1$进行简化。

简化的过程总结为3步:

  • 去掉运行时间中的所有加法常数。(例如 $n^2+n+1$,直接变为 $n^2+n$)
  • 只保留最高项。($n^2+n$变成 $n^2$)
  • 如果最高项存在但是系数不是1,去掉系数。($n^2$ 系数为 1)

所以,最终a、b和c合并而成的代码的时间复杂度为$O(n^2)$。

常用的时间复杂度的排序

列举了几种常见的算法时间复杂度的比较(又小到大):

$O(1)$常数阶 $<$ $O(\log n)$对数阶 $<$ $O(n)$线性阶 $<$ $O(n^2)$平方阶 $<$ $O(n^3)$立方阶 $<$ $O(2^n)$ 指数阶

拿时间换空间,用空间换时间

算法的时间复杂度和空间复杂度是可以相互转化的。

谷歌浏览器相比于其他的浏览器,运行速度要快。是因为它占用了更多的内存空间,以空间换取了时间。

算法中,例如判断某个年份是否为闰年时,如果想以时间换取空间,算法思路就是:当给定一个年份时,判断该年份是否能被4或者400整除,如果可以,就是闰年。

如果想以空间换时间的话,判断闰年的思路就是:把所有的年份先判断出来,存储在数组中(年份和数组下标对应),如果是闰年,数组值是1,否则是0;当需要判断某年是否为闰年时,直接看对应的数组值是1还是0,不用计算就可以马上知道。


版权属于:Veen Zhao

本文链接:https://blog.zwying.com/archives/36.html


—— 暂无评论 ——

OωO