说明：以下内容均参考：[美]Aditya Bhargava所著的《算法图解》
第一种使用的算法：二分查找。
二分查找的基本思想：每次都将要查找的序列砍掉一半，从而砍完整个序列至多需要 次，我们说算法的复杂度是
。
注意：复杂度中的 指的都是
。
注意：仅当列表是有序列表的时候，二分查找才管用。
二分查找算法的代码表示：
def binary_search(nums, target):
lo, hi = 0, len(nums)-1
while lo <= hi:
mid = (lo + hi) // 2 # 必须要取整，否则数组的索引会出错
if nums[mid] == target:
return mid
if nums[mid] < target:
# 这里的加1及后面的减1是为了避免lo和hi陷入某些数中出不去(比如lo=5, hi=6)
lo = mid + 1
else:
hi = mid - 1
return None
算法时间复杂度中的“线性时间”的意思是：算法的运行时间与序列的长度相同，序列有多长，运行时间就会有多长。其时间复杂度表示为 。
二分查找的运行时间为对数时间（ 时间）。其时间复杂度表示为
。
计算算法时间复杂度的目的在于知道算法运行时间的增速，即当序列的长度增加时，算法的运行时间额外增长得有多快。例如，当序列长度由一个较小的值变为一个较大的值时，线性时间复杂度的额外运行时间增加的非常多，而对数时间额外增加的非常少（几乎不受序列长度的影响），而且序列长度越长，这种差别就越大。因此时间复杂度在解决实际问题的过程中发挥着非常重要的作用。
大 表示法指出了算法需要执行的操作数（
可以理解为“Operation”），它指出了算法运行时间的增速，实际上计算的是操作数。（算法的速度指的并非时间，而是操作数的增速。在谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。）
大 表示法实际上指出的是最坏情况下的运行时间，它规定了算法运行时间的上限（比如，假设一个算法的运行时间是
，此时我们说这个算法的运行时间不可能超过
）。
常见的五大时间复杂度：
| 时间复杂度 | 运行时间 | 例子 |
|---|---|---|
| 快 | 二分查找 | |
| 较快 | 简单查找 | |
| 慢 | 快速排序 | |
| 较慢 | 选择排序 | |
| 非常慢 | 旅行商问题 |
常见大O运行时间的图示如图1所示：
图1：常见的大O运行时间
排序算法的重要性（或者说为什么要学排序？为什么有那么多的排序算法？）：因为很多算法仅在数据经过排序后才管用（比如二分查找）。
计算机内存的工作原理：（计算机就像是很多抽屉的集合体，每个抽屉都有地址。）当我们需要将数据存储到内存时，便会请求计算机提供存储空间，然后计算机给我们一个地址。当需要存储多项数据时，有两种基本方式——数组和链表。
数组中的元素在内存中是相连的。数组的这个特点正是导致数组在添加新元素时处理速度慢的根本原因：若数组原来所在的地址对应的内存后面没有多余的内存可供新元素加入，那么计算机就要为这个数组分配一个新的地址，以保证所有的元素都能紧密相连地放在内存中，此时，数组中原先已有的元素就要全部被搬到这个新的地址中。同理，若再向数组中添加新元素时，若原有内存还不够，则又要重新分配新地址并搬移原来的所有元素......因此，数组在动态添加新元素时会因为内存原因而严重影响速度。 解决这种问题的一种方法是：预先为数组分配足够的内存。但是这种方法有一个缺点：不知道要事先分配多少内存。如果分配多了则会导致内存浪费，分配少了就又要重新分配地址。
彻底解决这个问题的一种方法是链表。链表中的元素可存储在内存的任何地方：链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。在链表中添加新元素很容易：只需将其放入内存，并修改它前面的那个元素指向的地址。
数组和链表是优势互补的：链表的优势在插入元素方面（当插入一个新元素时很方便），但链表的查找就显得很不方便（当我们要查找链表中的某个元素时，我们是无法直接找到该元素的位置的，只能从链表的头结点开始，依次访问下一个节点，直到找到要找的元素，因此链表的查找会相当费时）； 而恰恰相反，数组的优势就在于查找元素（可以迅速地找到数组的任何元素），但其缺点是插入元素较慢。
当需要在中间插入元素时，链表是更好的选择。当需要删除元素时，链表也是更好的选择，因为只需要修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移。
链表仅支持顺序访问（即从第一个元素开始逐个地读取元素），而数组同时支持顺序访问和随机访问，因此数组的读取速度更快。实际情况大多要求能够随机访问，因此数组用的很多。
数组和链表操作的运行时间如下：
| 操作 | 数组 | 链表 |
|---|---|---|
| 插入 | ||
| 读取 | ||
| 删除 |
选择排序算法：
| 算法名称 | 选择排序 |
|---|---|
| 算法用途 | 排序 |
| 算法描述 | 首先遍历列表，从中找出元素的最大值，然后将其添加到一个新列表中；然后再次遍历剩余的列表，找出元素第二大的值，将其按顺序添加到新列表中；......直到所有元素被排成一个新的序列 |
| 时间复杂度 | 每次遍历的时间复杂度依次为： |
使用递归的好处是可以让程序更容易理解；使用循环的好处是程序的性能可能更高。
每个递归函数都有两部分：递归基和递归条件。递归基指的是函数什么时候不再调用自己，递归条件是指函数调用自己。每个递归函数必须要有递归基，否则会形成死循环。
栈的弹出指的是删除并读取。
栈的基本操作：压入（在栈顶添加一个新的元素）和弹出（删除并读取栈顶元素）。
每当程序调用一个函数时，计算机都将为该函数调用分配一块内存，而且该函数调用涉及到的所有变量的键和值也都将存储到内存中； 如果在这个函数里又有新的函数被调用，则先前那个函数会成为栈底，然后新来的这个函数被压入栈顶，并在栈顶保存新函数所涉及变量的键和值；如果又嵌套的有别的函数被调用，则重复此过程； 当栈顶的函数执行完时，计算机会将其从栈顶弹出（读取并删除）（每一次的return都相当于是弹出操作），然后前一个函数成为新的栈顶，当其执行完后再将其从栈顶弹出；如此直到栈被弹空，则所有函数执行完毕，程序返回最终结果。
栈的缺点：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，则意味着计算机存储了大量函数调用的信息。此时，可以考虑将递归换成循环来实现，或者使用尾递归（但并非所有的语言都支持尾递归）。
分而治之是一种通用的问题解决方法，它隶属于递归式问题解决方法。当面对一个问题束手无策时，不妨考虑一下分而治之。
使用分而治之解决问题的过程包括两个步骤：
（1）找出递归基，这个递归基必须尽可能简单；
（2）不断将问题分解（或者说缩小规模），直到符合递归基的要求。
分治策略的关键是如何缩小问题的规模。
分而治之其实并不是解决问题的算法，而是一种解决问题的思路。
快速排序使用了分治策略。
一个 list A 和一个空的 list 相加，得到的结果仍为 list A：
[1, 2, 3] + [ ] = [1, 2, 3]
快速排序的代码如下：
def quicksort(nums):
if len(nums) < 2:
return nums # 这是递归基：空的或只包含一个元素的数组是有序的
else:
pivot = nums[0] # 从nums中取出一个元素当做比较的基准
# 接下来将原数组分成两部分，一部分是小于pivot的，另一部分是大于pivot的
# smaller和bigger至少是空列表
smaller = [i for i in nums[1:] if i <= pivot]
bigger = [i for i in nums[1:] if i > pivot]
return quicksort(smaller) + [pivot] + quicksort(bigger)
快速排序是最快的排序算法之一，其平均时间复杂度为 ，但在最坏情况下，其时间复杂度和选择排序一样，均为
。
快速排序的性能严重依赖于每次选择的基准值 pivot。在最好情况下，快速排序的时间复杂度为 ，这发生在每次选择的基准值都能将余下的数组二等分，这样只需要
次就能将整个数组全部分完；而每次的排序操作耗时均为
，因此此时的时间复杂度为
； 而在最坏的情况下，快速排序的时间复杂度将达到
，这发生在每次选择的基准值都是剩余数组的最小值或最大值，这样每次只能减少数组的一个元素。如此一来，将需要 n 次才能将整个数组的长度减为0，非常耗时，而每次排序的时间复杂度均为
，因此这种情况下的整体时间复杂度为
。对这一解释的两个很形象的图示如图 2 - 1 和图 2 - 2 所示。
图 2 - 1：最坏情况下的时间复杂度：
图 2 - 2：最好情况下的时间复杂度：
字典的创建、添加与读取：
# 创建一个字典(以下两种方式等效)
book = dict()
book = {}
# 添加键值对
book['milk'] = 1.49
book['banana'] = 2.37
# 查找字典中的内容
# 字典的查找时间是O(1)时间
print(book['banana'])
# 用get方法可以获取字典中的内容
re = book.get('milk') # get中传入的是键，是string类型的值
字典的一种应用案例是缓存。缓存是一种常用的加速方式，所有大型网站都使用缓存，缓存的数据存储在散列表中。当需要提取缓存中的内容时，需要将页面的URL映射到页面数据。服务器缓存的一种代码示例如下所示：
cache = {}
def get_page(url):
if cache.get(url): # 这里用get而不是直接用cache[url]，是因为我们尚不确定cache中有没有url
return cache[url] # 返回缓存的数据
else:
data = get_data_from_server(url) # 如果url不在cache中，则让服务器生成这个url对应的页面
cache[url] = data # 将服务器生成的内容保存到缓存中以便后续查找时无需重复生成
return data
字典内部的工作机理：
散列函数负责将不同键所对应的值映射到不同的位置，但若不同键所对应的值映射到了同一个位置，就会引发冲突。
解决冲突的一种方法是：在冲突的位置处存储一个链表。但这里边存在的问题是：这些存储的链表不能过长，否则字典的速度将急剧下降。因此这对散列函数提出了很高的要求：散列函数要尽可能地将键均匀地映射到字典的不同位置，即要尽量避免冲突的发生。
在平均情况下，字典执行各种操作的时间都为 。
被称为常量时间，但常量时间并不意味着马上，而是说不管散列表多大，所需的时间都相同。
但在最坏情况下，字典的所有操作（包括查找、插入和删除）运行时间均为 。
网友评论