第八周学习

时间复杂度的表示
算法的时间复杂度的表示方式为:
O(频度)
这种表示方式称为大“O”记法。
注意,是大写的字母O,不是数字0。
对于上边的例子而言,a 的时间复杂度为O(1),b 的时间复杂度为O(n),c 的时间复杂度为为O(n2)。

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

简化的过程总结为3步:
去掉运行时间中的所有加法常数。(例如 n2+n+1,直接变为 n2+n)
只保留最高项。(n2+n 变成 n2)
如果最高项存在但是系数不是1,去掉系数。(n2 系数为 1)

所以,最终a、b和c合并而成的代码的时间复杂度为O(n2)。
常用的时间复杂度的排序
列举了几种常见的算法时间复杂度的比较(又小到大):
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)
拿时间换空间,用空间换时间
算法的时间复杂度和空间复杂度是可以相互转化的。

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

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

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

原文地址:https://www.cnblogs.com/123jjl/p/12808216.html