算法就是完成任务的一组指令，任何代码片段都可以说是算法。当然我们这里讨论的算法指是那些特别有趣的，比如速度特别快，或者能解决复杂问题。
工作中我们评价算法的合适不合适，该算法花费的时间是考虑的关键因素之一，也是我们研究算法的一个目标之一。我们需要知道该算法最多需要几次操作就可以达到目标，不同算法需要一个统一的表示法，大O就是用来表示有多少操作数的。至于为什么叫大O，可能是最开始做的人喜欢吧，以后就约定俗称的用了。本文从一个简单的例子来阐明这个问题。
例子：我们从100个有序元素列中查找某个元素并返回该元素的位置。元素就是整数吧，比较简单。
按照普通一个一个的比对，假如我们找的是第99元素，那就需要99次，表示为：O(99)，这是一种比较傻的算法。如果我们用 二分法查找，感觉能快不少。实际确实能快不少，我们每操作一次就能减少一半的元素数，比逐个查找比对强多了。
用二分查找元素数变化：100-50-25-13-7-4-2-1，最多需要7步就可以了
一般而言，对于包换n个元素的的列表，二分查找最多需要log2N次，普通的简单查找需要n次。这个二分查找的次数，用的是对数，底数为2，二分查找中一般用logn表示，例如 8个元素就是log8=3，1024个元素就是log1024=10；
大O表示法是一种特殊的表示法，指出了算法的运算速度有多快。上面的例子我们可以知道，简单的逐步查找是O(n)，二分查找是O(logn)，也就是随着元素数n的增加不同的算法操作数的变化快慢是不同的。
按照操作数从少到多的顺序，列出了5中常见的算法
1、O(logn)，对数时间，主要包括二分查找；
2、O(n)， 线性时间，就是简单查找。
3、O(n*logn) 快速排序：一种速度较快的排序算法
4、O(n2) 选择排序 ：一种速度较慢的排序算法
5、O(n！) 旅行商问题：一种非常慢的算法。
总结：算法的速度并不是时间，而是操作数的增速；谈论算法速度时候，我们说的是随着输入的增加，其运行时间将以什么样的速度增加；
以后章节补充每一种算法的详细内容
网友评论