跳到主要内容

为什么学习数据结构和算法？

提示
  1. 算法和数据结构的重要性：文章解释了学习数据结构和算法对提升编程技能和在大型科技公司找到工作的重要性。
  2. 算法和性能优化：介绍了算法是解决问题步骤的集合，强调了优化算法对提高代码执行效率和节省资源的重要性。
  3. 数据结构和算法的应用：展示了数据结构和算法在解决实际问题中的作用，如提高代码的可扩展性和处理大数据量。

这篇文章适合那些刚开始学习算法并想知道这将如何提升他们的职业/编程技能的人。也适合那些想知道为什么像谷歌、Facebook 和亚马逊这样的大公司会雇佣擅长优化算法的程序员的人。

什么是算法？​

通俗地说，算法只不过是解决问题的一系列步骤。它们本质上是一种解决方案。

例如，解决阶乘问题的算法可能看起来像这样：

问题：找出 n 的阶乘

初始化 fact = 1
对于范围 1 到 n 内的每个值 v：
    将 fact 乘以 v
fact 包含 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）

初始化 sum = 0
对于范围 1 到 1011（包含）内的每个自然数 n：
    将 n 加到 sum
sum 即为你的答案

代码（由 Alice 编写）

int findSum() {
    int sum = 0;
    for (int v = 1; v <= 100000000000; v++) {
        sum += v;
    }
    return sum;
}

Alice 和 Bob 对他们能够在几乎没有时间的情况下自己构建一些东西感到欣喜。让我们偷偷进入他们的工作空间，听听他们的对话。

**Alice:** 让我们运行这段代码，找出总和。**
Bob:** 我几分钟前运行了这段代码，但它仍然没有显示输出。这是怎么回事？

哎呀，出错了！计算机是最确定性的机器。回去再次尝试运行它并不会有帮助。所以让我们分析一下这段简单代码的问题所在。

对于计算机程序来说，最宝贵的两个资源是时间和内存。

计算机运行代码所需的时间是：

运行代码所需时间 = 指令数量 * 执行每条指令的时间

指令数量取决于你使用的代码，执行每条代码所需的时间取决于你的机器和编译器。

在这种情况下，执行的总指令数（假设为 x）是 x = 1 + (10^11 + 1) + (10^11) + 1，即 x = 2 * 10^11 + 3

假设计算机可以在一秒内执行 y = 10^8 条指令（这可能会根据机器配置有所不同）。运行上述代码所需的时间是

运行 1 条指令所需时间 = 1 / y 秒
运行 x 条指令所需时间 = x * (1/y) 秒 = x / y 秒

因此，
运行代码所需时间 = x / y
                     = (2 * 10^11 + 3) / 10^8 (超过 33 分钟)

是否有可能优化算法，使 Alice 和 Bob 不必每次运行这段代码时都等待 33 分钟？

我相信你已经猜到了正确的方法。前 N 个自然数的总和由公式给出：

总和 = N * (N + 1) / 2

Converting it into code will look something like this:

int sum(int N) {
    return N * (N + 1) / 2;
}

这个代码将只用一条指令就完成任务，无论值是多少。就算是超过宇宙中所有原子的总数，它也能立刻找到结果。

这种情况下解决问题所需的时间是 1/y（即 10 纳秒）。顺便说一句，氢弹的聚变反应需要 40-50 纳秒，这意味着即使有人在你运行代码的同时向你的电脑扔了一颗氢弹，你的程序也能顺利完成。 :)

注意： 计算机计算乘法和除法不是一条指令（而是几条指令）。我之所以说是一条，只是为了简化问题。

关于可扩展性的更多信息​

可扩展性是可扩展的能力，指的是算法/系统处理更大规模问题的质量。

考虑一下为 50 名学生设置教室的问题。最简单的解决方案是预定一个教室，搞个黑板，几支粉笔，问题就解决了。

但如果问题的规模增大了怎么办？如果学生人数增加到 200 呢？

解决方案仍然成立，但需要更多资源。在这种情况下，你可能需要一个更大的房间（可能是剧院）、一个投影屏幕和数字笔。

如果学生人数增加到 1000 呢？

当问题的规模增加时，解决方案要么失败，要么需要大量资源。这意味着，你的解决方案不具备可扩展性。

那么可扩展的解决方案是什么呢？

考虑像 Khanacademy 这样的网站，数百万学生可以同时观看视频、阅读答案，而不需要更多资源。所以，这个解决方案可以在资源紧张的情况下解决更大规模的问题。

如果你看我们找出前 N 个自然数之和的第一个解决方案，你会发现它不是可扩展的。因为它需要与问题规模的线性增长成比例地增加时间。这类算法也被称为线性可扩展算法。

我们的第二种解决方案非常可扩展，不需要使用更多时间来解决更大规模的问题。这些被称为恒定时间算法。

内存是昂贵的​

内存并不总是充裕的。在处理需要你存储或生成大量数据的代码/系统时，尽可能节省内存使用的算法至关重要。例如：在存储有关人的数据时，你可以通过只存储他们的出生日期而不是年龄来节省内存。你可以随时使用他们的出生日期和当前日期来计算年龄。

算法效率的示例​

以下是学习算法和数据结构使你能够做到的一些示例：

示例 1：年龄组问题​

像查找某个年龄段的人这样的问题可以通过稍微修改的二分查找算法轻松解决（假设数据已排序）。

逐个检查每个人是否属于给定年龄段的简单算法是线性可扩展的。而二分查找宣称自己是对数可扩展算法。这意味着如果问题的规模增加了两倍，解决它所需的时间只增加了一倍。

假设，为一组 1000 人找出某个

年龄的所有人需要 1 秒。那么对于 100 万人的一组，

  • 二分查找算法只需要2秒就能解决问题
  • 而朴素算法可能需要100万秒，约等于12天

同样的二分查找算法也用于寻找一个数字的平方根。

示例 2：魔方问题​

想象你正在编写一个程序来解决魔方问题。

这个看起来可爱的谜题有高达43,252,003,274,489,856,000个位置，而这仅仅是位置数！想象一下可以走的通往错误位置的路径数。

幸运的是，解决这个问题的方法可以用图数据结构来表示。有一种称为迪杰斯特拉算法的图算法，它能够让你在线性时间内解决这个问题。没错，你没听错。这意味着它允许你在最少的状态数内达到解决位置。

示例 3：DNA问题​

DNA是携带遗传信息的分子。它们由用罗马字符A、C、T和G表示的更小单元组成。

想象一下你在生物信息学领域工作。你的任务是找出特定模式在DNA链中的出现情况。

这是计算机科学学术界的一个著名问题。最简单的算法所需的时间与

(DNA链中的字符数量) * (模式中的字符数量)

成正比。

一个典型的DNA链有数百万这样的单位。哎！别担心。KMP算法可以在与以下时间成正比的时间内完成这项工作

(DNA链中的字符数量) + (模式中的字符数量)

* 操作符被 + 替换使得有了很大的变化。

假设模式是100个字符，你的算法现在快了100倍。如果你的模式是1000个字符，KMP算法将几乎快1000倍。也就是说，如果你之前能在1秒内找到模式的出现情况，现在只需要1毫秒。我们也可以从另一个角度来看。与其匹配1条链，你现在可以同时匹配1000条类似长度的链。

还有无数这样的故事......

最后的话​

通常，软件开发涉及每天学习新技术。在你的一个项目中使用这些技术时，你会学到大多数技术。然而，算法并非如此。

如果你不熟悉算法，你将无法识别是否可以优化你现在正在编写的代码。你应该提前了解它们，并在可能和关键的地方应用它们。

我们特别讨论了算法的可扩展性。一个软件系统由许多这样的算法组成。优化其中任何一个都会导致更好的系统。

然而，重要的是要注意，这不是使系统可扩展的唯一方法。例如，一种称为分布式计算的技术允许程序的独立部分一起在多台机器上运行，使其更具可扩展性。

最后于 更新