上查看所有课程
本文适合刚开始学习算法，并想知道算法对提升职业/编程技能有多大影响的人。也适合想知道谷歌、Facebook、亚马逊等大公司为何招聘在算法优化方面特别擅长的程序员的人。
什么是算法？
非正式地说，算法就是解决问题步骤的描述。它们本质上就是解决方案。
例如，解决阶乘问题的算法可能如下所示：
问题：求 n **的阶乘**
Initialize fact = 1
For every value v in range 1 to n:
Multiply the fact by v
fact contains the factorial of n
在这里，算法是用英语写的。如果用编程语言写，我们称之为**代码**。下面是用 C++ 编写计算数字阶乘的代码。
int factorial(int n) {
int fact = 1;
for (int v = 1; v <= n; v++) {
fact = fact * v;
}
return fact;
}
编程就是关于数据结构和算法。数据结构用于存储数据，而算法用于使用这些数据解决问题。
数据结构和算法 (DSA) 详细介绍了标准问题的解决方案，并让您深入了解每种解决方案的效率。它还教您评估算法效率的科学。这使您能够从多种选择中选择最佳方案。
使用数据结构和算法使您的代码可扩展
时间宝贵。
假设 Alice 和 Bob 正在尝试解决一个简单的计算前 1011 个自然数之和的问题。当 Bob 编写算法时，Alice 实现了一个证明，证明这就像批评唐纳德·特朗普一样简单。
算法（Bob 编写）
Initialize sum = 0
for every natural number n in range 1 to 1011(inclusive):
add n to sum
sum is your answer
代码（Alice 编写）
int findSum() {
int sum = 0;
for (int v = 1; v <= 100000000000; v++) {
sum += v;
}
return sum;
}
Alice 和 Bob 对他们几乎在短时间内就能构建出自己的东西感到兴奋。让我们潜入他们的工作空间，听听他们的对话。
Alice: Let's run this code and find out the sum. Bob: I ran this code a few minutes back but it's still not showing the output. What's wrong with it?
糟糕，出错了！计算机是最具确定性的机器。回过头来再次运行它不会有帮助。所以让我们分析一下这段简单的代码有什么问题。
计算机程序的两个最有价值的资源是**时间**和**内存**。
计算机运行代码所需的时间是：
Time to run code = number of instructions * time to execute each instruction
指令的数量取决于您使用的代码，每段代码的执行时间取决于您的机器和编译器。
在这种情况下，执行的总指令数（假设为 x）为 `x = 1 + (10^11 + 1) + (10^11) + 1`，即 `x = 2 * 10^11 + 3`。
我们假设一台计算机每秒可以执行 `y = 10^8` 条指令（具体取决于机器配置）。运行上述代码所需的时间为：
Time to run y instructions = 1 second
Time to run 1 instruction = 1 / y seconds
Time to run x instructions = x * (1/y) seconds = x / y seconds
Hence,
Time to run the code = x / y
= (2 * 1011 + 3) / 108 (greater than 33 minutes)
有没有可能优化算法，让 Alice 和 Bob 每次运行此代码时不必等待 33 分钟？
我敢肯定您已经猜到了正确的方法。前 N 个自然数的和由以下公式给出：
Sum = N * (N + 1) / 2
将其转换为代码如下所示：
int sum(int N) {
return N * (N + 1) / 2;
}
这段代码仅执行一条指令即可完成任务，无论值是多少。即使它大于宇宙中的原子总数。它将在短时间内找到结果。
在这种情况下，解决问题所需的时间是 `1/y`（即 10 纳秒）。顺便说一句，氢弹的聚变反应需要 40-50 纳秒，这意味着即使有人在您运行代码的同时向您的计算机扔了一枚氢弹，您的程序也将成功完成。 :)
注意：计算机执行乘法和除法需要几条指令（不是 1 条）。为了简单起见，我说的是 1 条。
更多关于可扩展性
可扩展性是规模加上能力，这意味着算法/系统处理更大规模问题的质量。
考虑为 50 名学生设置教室的问题。最简单的解决方案之一是预订一个房间，准备一块黑板、几块粉笔，问题就解决了。
但是，如果问题规模增加了怎么办？如果学生人数增加到 200 人怎么办？
该解决方案仍然有效，但需要更多资源。在这种情况下，您可能需要一个更大的房间（可能是剧院）、一个投影屏幕和一个数码笔。
如果学生人数增加到 1000 人怎么办？
当问题规模增加时，解决方案就会失败或使用大量资源。这意味着您的解决方案不是可扩展的。
那么什么是可扩展的解决方案呢？
考虑像 Khanacademy 这样的网站，数百万学生可以同时观看视频、阅读答案，而无需更多资源。因此，该解决方案可以在资源受限的情况下解决更大规模的问题。
如果我们计算前 N 个自然数之和的第一个解决方案，它就不是可扩展的。这是因为它需要随着问题规模的线性增长而线性增长时间。此类算法也称为线性可扩展算法。
我们的第二个解决方案非常可扩展，并且在解决更大规模的问题时不需要花费更多时间。这些被称为常数时间算法。
内存是昂贵的
内存并非总是充裕的。在处理需要您存储或生成大量数据的代码/系统时，您的算法能够尽可能节省内存的使用至关重要。例如：在存储有关人们的数据时，您可以仅存储他们的出生日期而不是年龄来节省内存。您始终可以使用他们的出生日期和当前日期即时计算。
算法效率的示例
以下是一些学习算法和数据结构可以做什么的例子：
示例 1：年龄组问题
诸如查找特定年龄组人群之类的问题，可以通过对 二分查找算法 进行少量修改（假设数据已排序）来轻松解决。
逐个遍历所有人员并检查其是否属于给定年龄组的朴素算法是线性可扩展的。而二分查找声称自己是对数可扩展算法。这意味着如果问题规模平方，解决它所需的时间只会加倍。
假设查找 1000 人群的特定年龄人群需要 1 秒。那么对于一百万人的群体，
- 二分查找算法只需要 2 秒即可解决问题。
- 朴素算法可能需要一百万秒，大约是 12 天。
相同的二分查找算法用于查找数字的平方根。
示例 2：魔方问题
想象一下，您正在编写一个程序来解决魔方的问题。
这个可爱的谜题有令人讨厌的 43,252,003,274,489,856,000 个位置，而这仅仅是位置！想象一下到达错误位置的路径数量。
幸运的是，解决这个问题的方法可以用 图数据结构 来表示。有一种称为 Dijkstra 算法 的图算法，它允许您在线性时间内解决此问题。是的，您没听错。这意味着它允许您在最少的状态下到达已解决的位置。
示例 3：DNA 问题
DNA 是一种携带遗传信息的分子。它们由用罗马字母 A、C、T 和 G 表示的小单位组成。
想象一下您在生物信息学领域工作。您的任务是找出 DNA 链中特定模式的出现次数。
这是计算机科学学术界的一个著名问题。而最简单的算法需要的时间与以下成正比：
(number of character in DNA strand) * (number of characters in pattern)
典型的 DNA 链有数百万个这样的单位。嗯！别担心。 KMP 算法 可以在与以下成正比的时间内完成：
(number of character in DNA strand) + (number of characters in pattern)
用 + 替换 * 运算符会产生很大差异。
考虑到模式有 100 个字符，您的算法现在快了 100 倍。如果您的模式有 1000 个字符，KMP 算法将快近 1000 倍。也就是说，如果您可以在 1 秒内找到模式的出现次数，那么现在只需要 1 毫秒。我们也可以换种说法。与其匹配 1 条链，不如同时匹配 1000 条长度相似的链。
还有无数这样的故事……
结语
通常，软件开发涉及每天学习新技术。您会在一个项目中学习其中许多技术。但是，算法并非如此。
如果您不熟悉算法，您将无法确定是否可以优化您当前编写的代码。您应该提前了解它们并在任何可能且关键的地方应用它们。
我们特别讨论了算法的可扩展性。软件系统由许多此类算法组成。优化其中任何一个都会带来更好的系统。
但是，值得注意的是，这并不是使系统可扩展的唯一方法。例如，一种称为 分布式计算 的技术允许程序的独立部分在多台机器上运行，使其更具可扩展性。