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

本文适用于那些刚开始学习算法并想知道学习算法对于提高他们的职业/编程技能会有多大影响的人。这也适用于那些想知道为什么像谷歌、Facebook 和亚马逊这样的大公司聘请特别擅长优化算法的程序员的人。

什么是算法？

非正式地，算法只不过是对解决问题的步骤的经验总结。它们本质上是一种解决方案。

例如，解决阶乘问题的算法可能如下所示：

问题：求 n 的阶乘

初始化阶乘变量为 1。
循环 1 到 n 中的所有的数，在每次循环中，阶乘变量等于继承变量乘以当前值。
最终的阶乘变量的值就是 n 的阶乘。

以上只是算法步骤的文字描述。如果它是用编程语言编写的，我们会将其称为代码。以下是用 C++ 编写的计算数字的阶乘的代码：

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

编程是关于数据结构和算法的。数据结构用于保存数据，而算法用于使用该数据解决问题。

数据结构和算法详细介绍了标准问题的解决方案，让您深入了解使用每个问题的效率。它还教你科学的评估算法效率。这使您可以在各种解决方案中作出最佳的选择。

使用数据结构和算法使您的代码可扩展

时间是宝贵的。

假设 Alice 和 Bob 试图解决一个简单的问题，即找到前 10¹¹ 个自然数的和。当鲍勃在编写算法时，爱丽丝实现了它，证明它就像批评唐纳德特朗普一样简单。

算法（由 Bob）

初始化 sum = 0
循环 从 1 到 100000000000 中的自然数 n:
    累加 n 到 sum
sum 就是答案

代码（由 Alice）

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

爱丽丝和鲍勃对自己感到欣喜若狂，他们几乎可以在短时间内建立自己的东西。让我们潜入他们的工作区，听听他们的谈话。

爱丽丝： 让我们运行这段代码并找出总和。

Bob： 几分钟前我运行了这段代码，但它仍然没有显示输出。它出什么问题了？

哎呀！出事了！计算机是最确定性的机器。返回并尝试再次运行它无济于事。那么让我们来分析一下这段简单的代码有什么问题。

计算机程序最宝贵的两种资源是时间和内存。

计算机运行代码所用的时间为：

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

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

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

让我们假设计算机可以在一秒钟内执行 y = 10^8 个指令（它可能因机器配置而异）。运行上述代码所花费的时间是：

运行代码所需的时间 = x/y（大于 16 分钟）

是否可以优化算法，使 Alice 和 Bob 每次运行此代码时不必等待 16 分钟？

我相信你已经猜到了正确的方法。计算前 N 自然数的总和的公式如下：

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

将其转换为代码将如下所示：

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

这段代码只在一条指令中执行，无论值是什么都能完成任务。让它大于宇宙中的原子总数，它会很快找到结果。

在这种情况下，解决问题所花费的时间是 1/y（10 纳秒）。顺便说一下，氢弹的聚变反应需要 40-50 纳秒，这意味着即使有人在您运行代码的同时向您的计算机扔氢弹，您的程序也会成功完成。

**注意：**计算机需要一些指令（不是 1）来计算乘法和除法。我说 1 只是为了简单起见。

内存很贵

内存并不总是充足的。在处理需要您存储或生成大量数据的代码/系统时，您的算法尽可能地节省内存使用量至关重要。例如：在存储关于人的信息时，您可以通过仅存储他们的出生日期而不是他们的年龄来节省内存。因为您总是可以使用他们的出生日期和当前日期动态计算它。

算法效率的例子

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

示例 1：年龄组问题

使用二进制搜索算法的一些修改版本（假设数据已排序）可以轻松解决诸如查找某个年龄段的人之类的问题。

一个一个地遍历所有人并检查它是否属于给定年龄组的朴素算法是线性可扩展的。而二分搜索声称自己是一种对数可扩展算法。这意味着如果问题的规模是平方的，那么解决它所花费的时间只会增加一倍。

假设，对于 1000 人的组，找到某个年龄的所有人需要 1 秒。然后对于 100 万人的组，

二分查找算法只需 2 秒即可解决问题
差劲的算法可能需要 100 万秒，也就是大约 12 天

示例 2：魔方问题

想象一下，您正在编写一个程序来寻找魔方的解法。

这个看起来很可爱的拼图令人讨厌地有 43252003274489856000 个位置，而这些只是位置！想象一下到达错误位置的路径数量。

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

示例 3：DNA 问题

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

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

这是计算机科学界的一个著名问题。而且，最简单的算法花费的时间与以下数字成比例：

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

一条典型的 DNA 链有数百万个这样的单元。诶！不用担心。KMP 算法则与以下数字成比例：

（DNA 链中的字符数）+（模式中的字符数）

把乘法运算符替换为加法改变了很多。

考虑到模式有 100 个字符， KMP 算法现在快了 100 倍。如果您的模式有 1000 个字符，则 KMP 算法将快近 1000 倍。也就是说，如果您能够在 1 秒内找到模式的出现，那么现在只需 1 毫秒。我们也可以换一种说法。您可以同时匹配 1000 条相似长度的链，而不是匹配 1 条链。

而且这样的案例数不胜数……

最后的话

通常，软件开发涉及每天学习新技术。在您的项目之一中使用这些技术时，您可以学习其中的大部分技术。但是，算法并非如此。

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

我们专门谈到了算法的可扩展性。一个软件系统由许多这样的算法组成。优化它们中的任何一个都会导致更好的系统。

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