1 快速算法和慢速算法的比较
当我们比较两个算法的速度时，想到的最直接方法就是比较两个算法完成同一个任务所用的时间。运行时间快的是快速算法，时间慢的是慢速算法。这个方法看似合理，实则有诸多问题：1、使用不同算力的计算机会影响运行时间，超级计算机执行一个加法运算只需10-9s，而普通计算机则需要10-5s。2、任务的复杂程度与运行时间并不是线性的关系，一个简单任务可能算法A运行时间短，一个复杂任务可能算法B运行时间短。
用什么评价方法才合理呢？这里引入了大O表示法，它指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间表示为O(n)。并没有时间单位s，这是因为大O法指的并非以秒为单位的速度。大O表示法让你能够比较操作次数，它表示出了算法运行时间的增速。如果换用二分法检查长为n的列表，二分查找需要执行log n次操作。使用大O表示法这个的运行时间则为O(log n)。
大O表示法指出了最糟糕情况下的运行时间。假设你查找电话簿中的A，如果A在电话簿第一位，一次就找到了，这是最佳的情形，但大O表示法说的是最糟糕的情形。因此，你可以说，在最糟糕的的情况下，必须查看电话簿中的每一个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。
2 一些常见的大O运行时间
下面按从快到慢的顺序列出经常会遇到的5种大O运行时间：
O(log n)，也叫对数时间，这样的算法包括二分查找；
O(n)，也叫线性时间，这样的算法包括简单查找；
O(n*log n)，这样的算法包括快速排序，一种速度较快的排序算法；
O(n2)，这样的算法包括选择排序，一种速度较慢的排序算法；
O(n!)，这样的算法包括旅行商问题的解决方案，一种非常慢的的算法。
image.png
参考资料
1、《算法图解》
2、《生物信息学算法导论》
网友评论