image.png
本文来源如何知道算法的运行速度
本篇笑点
已经2021年了，我的人生目标是30岁时，在北京拥有一套自己的房子。现在我的目标已经实现一半了，我已经三十岁了
你得知道这篇讲的些什么
本文1234字，阅读可能需要2分30秒
本篇主要提到理解算法的运行速度，以及知道什么是大O表示法。
说明
计算机是人大脑的延伸，它的存在主要是为了帮助我们解决问题。
而算法在计算机领域中，就是为了解决问题而指定的一些列简单的指令集合。
不同的算法需要不同的资源，例如执行时间和消耗。
如果一个算法执行时间需要好几年或者需要占用非常大的内存，那么这算法几乎毫无用处，即使有价值是由场景也非常有限。
因此，讨论一个算法的优劣的时候可以通过时间和空间两个维度来衡量，也就是常说的 时间复杂度 空间复杂度
在执行的时候，我们希望在执行时间和消耗内存越少越好，但是很多时候无法同时兼顾，需要在时间和空间之间做一定的取舍达到平衡。
大O表示法是什么
我们通过这样的表示法，可以清楚知道算法的速度。
假设，列表包含N个元素。简单查找需要检查每个元素，因此需要执行N此操作。使用大O表示法，这个运行时间为O(n)，单位秒呢？没有 大O表示法指的并非以秒的速度。大O表示法让你能够比较操作化，它指出了算法运行时间的增速。
再举一个例子，检查长度为n的列表。二分查找需要执行执行log n次操作，使用大O表示法，这个运行时间怎么标识呢？O(log n)。一般而言，大O表示法像下面这样。
image
这指出算法需要执行的操作数，之所以称为大O表示法，是因为操作前有大O，听起来像个笑话，但事实如此！
理解不同的大O运行时间
举例，在家使用纸和笔就能完成，假设画一个网格，包含16个格子。
image.png
算法1. 一种方式是以每次画一个的方式画十六个格子。记住大O表示法，计算的是操作数。在这个示例中，画一个格子是一个操作，需要花16个格子呢，如果每次画一个需要执行多少次操作呢？先思考一下待会解答
算法2. 将纸折起来，折一次就是一个操作。第一次对折相当于配两个格子，继续对折4次后打开，便得到漂亮的网格！每次折一次，格子数翻倍，所以折四次便能得到16个格子！
解答 算法1的运行时间是O(n)。算法2 的算法时间是O(log n)。
常见的大O运行时间
从快到慢的顺序列出了会经常遇到的5种大O运行时间。
- O(log n) 也叫对数时间，这样的算法包括二分查找。
- O(n)也叫线性时间，这样的算法包括简单查找。
- O(n * log n) 速度较快的排序算法
- O(n²) 速度较慢的排序算法
- O(n!) 速度慢的算法。
总结
打起精神来，看看这篇你都get到了什么
1.算法的速度指的并非时间，而是操作数的增速。
2.谈论算法的速度时，我们说的是随着舒服的增加，其运行时间将以什么样的速度增加。
3.算法的运行时间，用大O表示法。
4.O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快的越多
附言
本篇如有错误，请及时指出，马上修改。
非常非常重要的事情
本文首发于【黑壳博客】，文章持续更新，可以微信搜索【黑壳博客】点个关注 文章第一时间阅读。
网友评论