算法是什么？
算法就是完成一组特定任务的方法。
比如将大象放进冰箱需要三步：
打开冰箱
将大象放进冰箱
关闭冰箱
这就是一种算法。
如果用计算机语言来叙述，就是任何实现某种功能的代码片段都可以称之为算法。
一个程序员应该掌握大概50种基本算法，但目前我们属于初级阶段，先掌握一些简单有趣的算法，为日后进一步的算法学习打下基础。
二分查找
比如我要在字典（这里是真实的字典，不是Python的dict类型）中查找以O为拼音首字母的汉字，我会从字典的中间附近开始翻阅，因为我知道字母O在26个字母的中间附近，这会提高我的查找效率。在这里，我就运用了二分查找的思想。
二分查找是一种算法，它的思想就是：
在一个有序的元素列表中，每次将查找的元素与元素列表的中间元素作比较
如果等于中间元素，则查找完毕
若比中间元素大，则在大于中间元素的一半中重复步骤1
若比中间元素小，则在小于中间元素的一半中重复步骤1
重复步骤2或3或4，直至查找完毕
注释：仅当列表是有序的时候，二分查找才管用。
一般而言，对于包含n个元素的有序列表，用二分查找最多需要㏒₂n步，而简单查找最多需要n步。
我们一般使用大O表示法来表征算法的运行时间，其中㏒一般指的是㏒₂
现在我们来看看如何使用Python来编写二分查找的代码，这里以一个简单的数组示例：
def binary_search(list, item):
"""定义一个二分查找的函数"""
# low 和 high用于跟踪要在其中查找的列表部分
low = 0
high = len(list) - 1
while low <= high:
global n
mid = int((low + high)/2) # 检查中间的元素
guess = list[mid]
n = n + 1 # 时间复杂度计数
if guess == item # 找到了元素
return mid
elif guess > item: # 猜的数大了
high = mid - 1
else: # 猜的数小了
low = mid + 1
return None # 没有查询到指定的元素
n = 0
my_list = [1, 3, 5, 7, 9, 10]
result = binary_search(my_list, 7) # 指定元素的位置
print("查询结果：", result)
print("时间复杂度：", n)</pre>
执行结果：
查询结果： 3
时间复杂度： 3
需要说明的是，二分查找的查询结果是返回待查找元素在列表中的位置，当然，列表是以0开始标记的。
大O表示法
大O表示法是一种特殊的表示法， 它指出了算法的运行速度有多快。例如，假设列表包含n个元素，简单查找需要检查每个元素，因此需要执行n次操作，使用大O表示法，它的运行时间为O(n)，它的单位是秒么？不是，它没有单位。
大O表示法指的并非以秒为单位的速度。它指的是算法运行时间的增速（强调增速）。
比如，为检查长度为n的列表，二分查找需要执行㏒n次操作。使用大O表示法，它的运行时间为O(㏒n)。
我们来对比一下简单查找和二分查找的增速差异（假设检查一个元素需要1毫秒）：
这里就能看出两者运行时间的增速有着天壤之别
大O表示法指出的是平均情况下的运行时间
比如，简单查找的运行时间用大O表示法是O(n)，但是如果列表的第一个元素就是待查找元素，那么简单查找的运行时间就是O(1)。但这只是特殊情况，一般而言，简单查找的运行时间是O(n)。
一些常见的大O运行时间
下面从快到慢列举了5种常见的大O运行时间
O(㏒ n)， 也叫对数时间，这样的算法包括二分查找
O(n)， 也叫线性时间，这样的算法包括简单查找
O(n*㏒n)， 这样的算法包括快速排序--一种速度较快的排序算法
O(n²)， 这样的算法包括选择排序--一种速度较慢的排序算法
O(n!)， 这样的算法包括旅行商问题的解决方案--一种非常慢的算法
旅行商问题
旅行商问题是计算机科学领域一个十分著名的问题。这个问题是怎样的呢？
有一位旅行商，他要前往5个城市。
画的图好丑
同时要确保旅程最短。为此，可以考虑去往这些城市的各种可能顺序。高中学过的排列组合的知识告诉我们，5个城市有120种不同组合。因此，在涉及5个城市时，需要执行120次操作。涉及6个城市时，需要执行720次操作。
推而广之，涉及n个城市时，需要执行n！（n的阶乘）次操作才能计算出结果。因此运行时间为O(n!)，即阶乘时间。在涉及的城市较多时，这个算法根本无法在有效的时间内计算出结果。面对这种问题，我们只能去找出近似答案~
小结
二分查找的速度比简单查找快得多
算法的运行时间不是以秒为单位的
算法的运行时间是从其增速的角度衡量的
算法的运行时间使用大O表示法表示
每天学习一点点，每天进步一点点。
