算法图解笔记

大O表示法

大O表示法讨论运行时间时，log指的都是log2。

大O表示法是一种特殊的表示法，指出了算法的速度有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

大O表示法指出了最糟情况下的运行时间。

除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。

一些常见的大O运行时间

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
• O(n*n)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
• O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

n! 表示 n 的阶乘。 n!=1×2×3×…×n。

下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间:

上述图表中的时间是基于每秒执行10次操作计算得到的。这些数据并不准确，这里提供它们只是想让你对这些运行时间的差别有大致认识。实际上，计算机每秒执行的操作远不止10次。

小结

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示。
• O(log n) 比 O(n) 快，当需要搜索的元素越多时，前者比后者快得越多。

数组与链表

数组的特点：

• 数组中所有元素的类型都必须相同(都为int、double等)。
• 数组中的元素在内存中都是相连的。
• 数组支持顺序访问和随机访问。
• 数组的读取速度很快。

链表的特点：

• 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
• 在链表中添加元素很容易:只需将其放入内存，并将其地址存储到前一个元素中。
• 链表只支持顺序访问。
• 链表的插入和删除速度很快。

常见数组和链表操作的运行时间

	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

递归

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。 递归只是让解决方案更清晰，并没有性能上的优势。

• 递归指的是调用自己的函数。
• 每个递归函数都有两个条件：基线条件和递归条件。
• 栈有两种操作：压入和弹出。
• 所有函数调用都进入调用栈。
• 调用栈可能很长，这将占用大量的内存。

快速排序

分而治之

分而治之 (divide and conquer，D&C)，一种著名的递归式问题解决方法。

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

• 找出基线条件，这种条件必须尽可能简单。
• 不断将问题分解(或者说缩小规模)，直到符合基线条件。

编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

快速排序

def quicksort(array):
	if len(array) < 2:
		return array  # 基线条件:为空或只包含一个元素的数组是“有序”的
	else:
		pivot = array[0] 递归条件
		less = [i for i in array[1:] if i <= pivot] # 由所有小于基准值的元素组成的子数组
		greater = [i for i in array[1:] if i > pivot] # 由所有大于基准值的元素组成的子数组
   		return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

小结

• 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
• 快速排序在最糟糕的情况下，算法的运行时间为O(n) * O(n) = O(n2)。
• 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n) 快得多。

散列表（哈希表）

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

hash就是找到一种数据内容和数据存放地址之间的映射关系。

当使用哈希表hashtable(key，value) 进行查询的时候，就是使用哈希函数将关键码key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。

应用

• 将散列表用于查找，例如：DNS解析
• 防止重复
• 将散列表用作缓存

哈希冲突

哈希冲突(hash collision)：哈希函数将两个不同的键映射到同一个索引的情况。

哈希冲突是不可避免的，如果遇到冲突，最常用的解决办法就是开放定址法和链地址法。

开放定址法

开放定址法是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入。

但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(空间/插入数据)>=1。

链地址法

链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。

性能

在平均情况下，散列表执行各种操作的时间都为O(1)。O(1)被称为常量时间。你以前没有见过常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。

在最糟情况下，散列表所有操作的运行时间都为O(n)——线性时间，这真的很慢。我们来将散列表同数组和链表比较一下。

	数组	链表	散列表平均情况	散列表最糟情况
查找	O(1)	O(n)	O(1)	O(n)
插入	O(n)	O(1)	O(1)	O(n)
删除	O(n)	O(1)	O(1)	O(n)

在平均情况下，散列表的查找(获取给定索引处的值)速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点!但在最糟情况下，散列表的各种操作的速度都很慢。因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有:

• 较低的填装因子
  • 填装因子：散列表元素数 / 位置总数
  • 填装因子大于1意味着元素数量超过了数组的位置数。
  • 一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度(resizing)，通常将数组增长一倍。
  • 一个不错的经验规则是:一旦填装因子大于0.7，就调整散列表的长度。
• 良好的散列函数
  • 最理想的情况是：散列函数将键均匀地映射到散列表的不同位置。
  • 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很 好，这些链表就不会很长!

广度优先搜索

找到关系最近的芒果销售商。