如何知道算法的运行速度?

本文来源如何知道算法的运行速度

本篇笑点

已经2021年了,我的人生目标是30岁时,在北京拥有一套自己的房子。现在我的目标已经实现一半了,我已经三十岁了

你得知道这篇讲的些什么

本文1234字,阅读可能需要2分30秒

本篇主要提到理解算法的运行速度,以及知道什么是大O表示法。

说明

计算机是人大脑的延伸,它的存在主要是为了帮助我们解决问题。
而算法在计算机领域中,就是为了解决问题而指定的一些列简单的指令集合。
不同的算法需要不同的资源,例如执行时间和消耗。
如果一个算法执行时间需要好几年或者需要占用非常大的内存,那么这算法几乎毫无用处,即使有价值是由场景也非常有限。
因此,讨论一个算法的优劣的时候可以通过时间和空间两个维度来衡量,也就是常说的 时间复杂度 空间复杂度
在执行的时候,我们希望在执行时间和消耗内存越少越好,但是很多时候无法同时兼顾,需要在时间和空间之间做一定的取舍达到平衡。

大O表示法是什么

我们通过这样的表示法,可以清楚知道算法的速度。
假设,列表包含N个元素。简单查找需要检查每个元素,因此需要执行N此操作。使用大O表示法,这个运行时间为O(n),单位秒呢?没有 大O表示法指的并非以秒的速度。大O表示法让你能够比较操作化,它指出了算法运行时间的增速。

再举一个例子,检查长度为n的列表。二分查找需要执行执行log n次操作,使用大O表示法,这个运行时间怎么标识呢?O(log n)。一般而言,大O表示法像下面这样。

这指出算法需要执行的操作数,之所以称为大O表示法,是因为操作钱有大O,挺起来像个笑话,但事实如此!

理解不同的大O运行时间

举例,在家使用纸和笔就能完成,假设画一个网格,包含16个格子。

算法1. 一种方式是以每次画一个的方式画十六个格子。记住大O表示法,计算的是操作数。在这个示例中,画一个格子是一个操作,需要花16个格子呢,如果每次画一个需要执行多少次操作呢?先思考一下待会解答

算法2. 将纸折起来,折一次就是一个操作。第一次对折相当于配两个格子,继续对折4次后打开,便得到漂亮的网格!每次折一次,格子数翻倍,所以折四次便能得到16个格子!

解答 算法1的运行时间是O(n)。算法2 的算法时间是O(log n)。

常见的大O运行时间

从快到慢的顺序列出了会经常遇到的5种大O运行时间。

  1. O(log n) 也叫对数时间,这样的算法包括二分查找。
  2. O(n)也叫线性时间,这样的算法包括简单查找。
  3. O(n * log n) 速度较快的排序算法
  4. O(n²) 速度较慢的排序算法
  5. O(n!) 速度慢的算法。

###总结
打起精神来,看看这篇你都get到了什么
1.算法的速度指的并非时间,而是操作数的增速。
2.谈论算法的速度时,我们说的是随着舒服的增加,其运行时间将以什么样的速度增加。
3.算法的运行时间,用大O表示法。
4.O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快的越多

附言

本篇如有错误,请及时指出,马上修改。

非常非常重要的事情

本文首发于【黑壳博客】,文章持续更新,可以微信搜索【黑壳博客】点个关注 文章第一时间阅读。

黑壳博客 blog.bhusk.com

E-mail:keshu@bhusk.com

本文由 黑壳博客的壳叔 创作或转载,采用 知识共享署名 3.0 中国大陆许可协议 进行许可。

可自由转载、引用,但需署名作者且注明文章

留下你的脚步
推荐阅读