数据结构与算法 概述
1976年，一个瑞士计算机科学家写一本书《Algorithms + Data Structures = Programs》。即：算法 + 数据结构 = 程序。40多年过去了，这个等式依然成立。
什么是数据结构？
数据结构(data structure)是计算机存储、组织数据的方式。对于特定的数据结构(比如数组)，有些操作效率很高(读某个数组元素)，有些操作的效率很低(删除某个数组元素)。程序员的目标是为当前的问题选择最优的数据结构。
具有以下设计目标。
- 空间占用尽量少，以节省计算机内存。
- 数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。
- 提供简洁的数据表示和逻辑信息，以便算法高效运行。
什么是算法？
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。（《大话数据结构》）
它具有以下特性。
- 问题是明确的，包含清晰的输入和输出定义。
- 具有可行性，能够在有限步骤、时间和内存空间下完成。
- 各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。
数据结构与算法的关系
数据结构与算法高度相关、紧密结合，具体表现在以下三个方面。
- 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
- 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
- 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。
大O表示法
每次介绍算法时，我都将讨论其运行时间。一般而言，应选择效率最高的算 法，以最大限度地减少运行时间或占用空间。
大O表示法是一种特殊的表示法，指出了算法的速度有多快。
例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法， 这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法 让你能够比较操作数，它指出了算法运行时间的增速。
但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应 的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。
O(n)时间意味着查看列表中 的每个元素一次。例如，对乐队列表进行简单查找时，意味着每个乐队都要查看一次。
对数：
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
- O(log n)，也叫对数时间，这样的算法包括二分查找。
- O(n)，也叫线性时间，这样的算法包括简单查找。
- O(n * log n)，这样的算法包括快速排序——一种速度较快的排序算法。
- O(n2)，这样的算法包括选择排序——一种速度较慢的排序算法。
- O(n!)，这样的算法包括旅行商问题的解决方案——一种非常慢的算法。
小结：
- 算法的速度指的并非时间，而是操作数的增速。
- 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示。
- O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
递归
- 递归指的是调用自己的函数。
- 每个递归函数都有两个条件：基线条件和递归条件。
- 所有函数调用都进入调用栈。
- 栈有两种操作：压入和弹出。
- 调用栈可能很长，这将占用大量的内存。
调用栈
递归函数用调用栈进行多次调用，当符合条件时才开始依次将一层一层调用返回。先通过一次次调用，将栈垒高，然后再从最上方一层一层地返回。整个过程有些像倒U型。
调用栈期间会持续累积调用信息，很占计算机内存。递归会持续记录调用状态，在返回条件触发之前并不会执行这些调用。这就有点像Spark里面的转换算子和行动算子，在行动之前，转换惰性调用，只记录前后的依赖关系，并不会进行计算操作。
使用栈虽然很方便，但是也要付出代价：存储详尽的调用信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。
- 重新编写代码，转而使用循环。
- 使用尾递归。注意，并非所有的语言 都支持尾递归。