算法图解阅读笔记

# 比较数组和链表

链表存在一个问题。在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2 的地址，再访问元素#2 并从中获取元素#3 的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高:你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低

数组与此不同:你知道其中每个元素的地址。例如，假设有一个数组，它包含五个元素，起始地址为 00，那么元素05 的地址是多少呢?

只需执行简单的数学运算就知道:04。需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问第五个元素。

下面列出了常见的数组和链表操作的运行时间。

使用场景：数组用得很多，因为它支持随机访问。有两种访问方式:随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只能顺序访问:要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机 10 访问意味着可直接跳到第十个元素。

# 对递归的理解

Leigh Caldwell 在 Stack Overflow 上说的一句话:“如果使用循环，程序的性能可能更高;如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

# 平均情况和最糟情况

快速排序的性能高度依赖于你选择的基准值。假设你总是将第一个元素用作基准值，且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序。

注意，数组并没有被分成两半，相反，其中一个子数组始终为空，这导致调用栈非常长。现在假设你总是将中间的元素用作基准值，在这种情况下，调用栈如下。

调用栈短得多!因为你每次都将数组分成两半，所以不需要那么多递归调用。你很快就到达了基线条件，因此调用栈短得多。

第一个示例展示的是最糟情况，而第二个示例展示的是最佳情况。

在最糟情况下，栈长为 O(n)，而在最佳情况下，栈长为 O(log n)。

现在来看看栈的第一层。你将一个元素用作基准值，并将其他的元素划分到两个子数组中。这涉及数组中的全部 8 个元素，因此该操作的时间为 O(n)。在调用栈的第一层，涉及全部 8 个元素，但实际上，在调用栈的每层都涉及 O(n)个元素。

即便以不同的方式划分数组，每次也将涉及 O(n)个元素。

因此，完成每层所需的时间都为 O(n)。

在这个示例中，层数为 O(log n)(用技术术语说，调用栈的高度为 O(log n))，而每层需要的时间为 O(n)。因此整个算法需要的时间为 O(n) _ O(log n) = O(n log n)。这就是最佳情况。
在最糟情况下，有 O(n)层，因此该算法的运行时间为 O(n) _ O(n) = O(n2)。

知道吗?这里要告诉你的是，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为 O(n log n)。

快速排序是最快的排序算法之一，也是分而治之(divide and conquer，D&C) 典范。

# 散列冲突

大多数语言都提供了散列表实现，你不用知道如何实现它们。有鉴于此，我就不再过多地讨论散列表的内部原理，但你依然需要考虑性能!要明白散列表的性能，你得先搞清楚什么是冲突。

你可能已经看出了问题。如果你要将苹果的价格存储到散列表中，分配给你的是第一个位置。

接下来，你要将香蕉的价格存储到散列表中，分配给你的是第二个位置。

不好，这个位置已经存储了苹果的价格! 怎么办? 这种情况被称为冲突(collision):给两个键分配的位置相同。这是个问题。如果你将鳄梨的价格存储到这个位置，将覆盖苹果的价格，以后再查询苹果的价格时，得到的将是鳄梨的价格!冲突很糟糕，必须要避免。处理冲突的方式很多，最简单的办法如下:如果两个键映射到了同一个位置，就在这个位置存储一个链表。

在这个例子中，apple 和 avocado 映射到了同一个位置，因此在这个位置存储一个链表。在需要查询香蕉的价格时，速度依然很快。但在需要查询苹果的价格时，速度要慢些:你必须在相应的链表中找到 apple。如果这个链表很短，也没什么大不了——只需搜索三四个元素。但是，假设你工作的杂货店只销售名称以字母 A 打头的商品。