本文是在阅读Aditya Bhargava先生算法图解一书所做的总结，文中部分代码引用了原文的代码，在此感谢Aditya Bhargava先生所作出的这么简单的事例，对基础算法感兴趣的朋友可以阅读原文。由于本人也是编程初学者，所以本书比较浅显易懂，所介绍的算法配上插图也十分易懂，这里只是介绍几种最基础的算法由浅入深以帮助理顺一些简单的思维逻辑。

　　算法是一组完成任务的指令。任何代码片段都可视为算法，我们这里讨论的算法要么速度快，要么能解决有趣的问题，要么兼而有之。

　　二分查找是一种算法，其输入是一个有序的元素列表，如果要 查找的元素包含在列表中，二分查找返回其位置；否则返回Null。

　　二分法很好理解，如果让你猜出100以内指定的某个值的话，怎样可以做到用最少的次数寻找到。可能有人觉得可能一次就可以找到，但是最糟可能要猜100次哦。

　　这种问题使用二分法就很简便了，每次取中间值以缩小查找范围，这样7步以内必定可以找到答案。

　　如果这个问题扩大到4亿的话，无疑二分法可要优秀的多。一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。

　　二分法的有点事查找速度快，但是仅当列表是有序的时候，二分查找才管用。

　　对于这个猜数字的游戏使用二分法思想完成的代码如下：

　　大O表示法是一种特殊的表示法，指出了算法的速度有多快。由于不同算法运行时间的增速不同，所以使用大O表示法来看时间增速更为科学直观。

　　例如假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。之所以称为大O表示法，是因为操作数前有个大O。。。这是真的。

　　简单查找的运行时间总是为O(n)。在电话簿查找Adit时，一次就找到了，这是最佳的情形，即O（1），但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。

　　? O(log n)，也叫对数时间，这样的算法包括二分查找。

　　? O(n)，也叫线性时间，这样的算法包括简单查找。

　　? O(n * log n)，这样的算法包括快速排序。

　　? O(n2 )，这样的算法包括选择排序。

　　? O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案。

　　使用这几种算法绘制一个16格的网格需要的时间如下：

　　速度由快到慢，当然只是针对这个问题而言。

　　? 算法的速度指的并非时间，而是操作数的增速。

　　? 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

　　? 算法的运行时间用大O表示法表示。

　　? O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

　　这着实困扰着很多人，一位旅行商要去往5个城市，如何确保旅程最短，5个城市有120种不同的排列方式。涉及n个城市时，需要执行n!（n的阶乘）次操作才能计算出结果。因此运行时间为O(n!)，即阶乘时间。

　　很多算法仅在数据经过排序后才管用。当然很多语言都内置了排序算法，因此你基本 上不用从头开始编写自己的版本。

　　需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。

　　数组中的内存必须是相连的，这意味着增加元素的时候如果紧跟着的那个内存被占用了，那就只能重新寻找可容纳的连续地址，如果没有这么长的连续地址结果还存不了，所以计算机在存数组时还预留了空间，你只要三个内存，但是我给你十个。即使如此额外请求的位置可能根本用不上，这将浪费内存，你没有使用，别人也用不了。而且待办事项超过10个后，你还得转移。

　　链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。在链表中添加元素很容易：只需将其放入内存，并将其地址存储到前一个元素中，删除也是如此。但是链表在读取上要明显弱于数组，要读取最后一个内存的内容必须要按顺序依次读到最后一个位置为止，数组可以随意读取中间任意位置的内容（因为知道第一块内存地址可以推出第几块地址的位置，他们是连续的）。

数组与链表的操作运行时间

 　　数组和链表哪个用得更多呢？显然要看情况。但数组用得很多，因为它支持随机访问，很多情况都要求能够随机访问，而不是顺序访问。

　　比如网易云音乐要根据你听歌的次数排序你喜欢的音乐，可以每次都循环列表，每次取出最高次数的音乐放入新列表，直到原列表为空时结束。则总时间为1/2O（n**2），大O法省略常数，所以也就是时间为O（n**2）。

　　选择排序的代码：

　　注：同一数组的元素类型都必须相同。

　　递归指的是调用自己的函数，递归只是让解决方案更清晰，并 没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。Leigh Caldwell在Stack Overflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能 更容易理解。如何选择要看什么对你来说更重要。”

　　编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线 条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己的条件，从而避免形成无限循环。

　　这个概念大家一定都比较清楚，这是经常使用的两种编程概念，堆也叫队列，指的是先进先出，栈则相反指的是后进先出，可以想一想python中的嵌套函数的调用，里层的函数是后定义的但是却先执行完，执行完有返回外层函数，这个调用函数就是调用栈的概念。规范的说他们只有压入和弹出两种状态。

　　使用栈也存在一些缺点，存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。那么你只能使用循环完成或者尾递归（这个高级方法我还不会）。

　　假设要将一块土地均匀分成方块，并且确保方块最大。可以使用D&C策略。D&C算法是递归的。

　　使用D&C解决问题的过程包括两个步骤：

　　 (1) 找出基线条件，这种条件必须尽可能简单。

　　(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。

　　根据D&C的定义，每次递归调用都必须 缩小问题的规模。这个问题的基线条件就是一条边的长度是另一条边的整数倍。以短边为基准，在长边取短边*n的最大取值，剩下的部分依次按上述操作，直到最后长边为短边的整数倍位置短边**2就是最大方形了。

　　D&C的工作原理：

　　(1) 找出简单的基线条件；

　　(2) 确定如何缩小问题的规模，使其符合基线条件。

　　D&C并非可用于解决问题的算法，而是一种解决问题的思路。

　　快速排序使用了D&C。对排序算法来说，基线条件为数组为空或只包含一个元素。

　　首先，从数组中选择一个元素，这个元素被称为基准值；

　　接下来，找出比基准值小的元素以及比基准值大的元素。

　　再对这两个子数组进行快速排序，直到满足基线条件。

　　注：归纳证明是一种证明算法行之有效的方式，它分两步：基线 条件和归纳条件。

　　快速排序的最糟情况运行时间为O（n**2），与选择排序一样慢，但是他的平均排序时间为O（n*log n）。而合并排序总是O（n*log n）。但是这不是绝对的，合并排序的常量总是大于快速排序，所以一般情况下认为快速排序更快。