# 为什么要学习数据结构和算法？ > 原文： [https://www.programiz.com/dsa/why-algorithms](https://www.programiz.com/dsa/why-algorithms) #### 在本文中，我们将学习为什么每个程序员都应借助示例来学习数据结构和算法。 本文适用于刚开始学习算法并想知道对提高其职业/编程技能有多大影响的人员。 对于那些想知道为什么 Google，Facebook 和 Amazon 这样的大公司为何聘请非常擅长优化算法的程序员的人也是如此。 * * * ## 什么是算法？ 非正式地讲，算法只不过是解决问题的步骤。 它们本质上是一个解决方案。 例如，解决阶乘问题的算法可能如下所示： **问题**：找到`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 正在尝试解决一个简单的问题，即找到前`10^11`个自然数之和。 当鲍勃（Bob）编写算法时，爱丽丝（Alice）实现了该算法，证明它就像批评唐纳德·特朗普（Donald Trump）一样简单。 **算法（由 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）感到欣喜若狂，他们几乎可以在短时间内建立自己的东西。 让我们潜入他们的工作区，听听他们的谈话。 > 爱丽丝：让我们运行这段代码，找出总和。 鲍勃：我在几分钟前运行了这段代码，但仍未显示输出。 它出什么问题了？ 哎呀！出事了！ 计算机是最确定的机器。 返回并尝试再次运行它将无济于事。 因此，让我们分析一下此简单代码的问题所在。 计算机程序最有价值的两个资源是**时间**和**存储器**。 计算机运行代码所需的时间为： ``` 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 taken to run code = x/y (greater than 16 minutes) ``` 是否可以优化算法，使 Alice 和 Bob 不必每次运行此代码都等待 16 分钟？ 我相信您已经猜到了正确的方法。 第一个`N`个自然数的总和由下式给出： ``` Sum = N * (N + 1) / 2 ``` 将其转换为代码将如下所示： ``` int sum(int N) { return N * (N + 1) / 2; } ``` 该代码仅用一条指令执行，无论值是多少，都可以完成任务。 让它大于宇宙中原子的总数。 它将很快找到结果。 在这种情况下，解决问题所需的时间为`1/y`（10 纳秒）。 顺便说一句，氢弹的融合反应需要 40-50 ns，这意味着即使有人在运行代码的同时向计算机上扔了氢弹，程序也将成功完成。 :) **注意**：计算机采用一些指令（而非 1）来计算乘法和除法。 我只是为了简单起见说 1。 * * * ### 有关可扩展性的更多信息 可扩展性是规模加能力，这意味着处理较大问题的算法/系统的质量。 考虑建立一个有 50 个学生的教室的问题。 最简单的解决方案之一是预订房间，拿起黑板，几支粉笔，问题就解决了。 **但是，如果问题的规模增加了怎么办？ 如果学生人数增加到 200，该怎么办？** 该解决方案仍然有效，但需要更多资源。 在这种情况下，您可能需要更大的房间（可能是剧院），投影仪屏幕和数字笔。 **如果学生人数增加到 1000，该怎么办？** 当问题的规模增大时，该解决方案将失败或使用大量资源。 这意味着您的解决方案不可扩展。 **那么什么是可扩展的解决方案？** 考虑一个像 [Khanacademy](https://www.khanacademy.org/) 这样的网站，数百万学生可以同时观看视频，阅读答案，并且不需要更多资源。 因此，该解决方案可以解决资源紧缩下规模较大的问题。 如果您看到我们找到第一个`N`个自然数之和的第一个解决方案，则该解决方案不可扩展。 这是因为它要求时间随时间线性增长，而问题的大小则线性增长。 这种算法也称为线性可扩展算法。 我们的第二个解决方案具有很高的可扩展性，不需要花费更多的时间来解决更大的问题。 这些被称为恒定时间算法。 * * * ### 内存昂贵 内存并不总是足够可用。 在处理需要您存储或产生大量数据的代码/系统时，对于算法而言，尽可能地节省内存使用至关重要。 例如：在存储有关`Person`的数据时，您可以通过仅存储其`age`而不是出生日期来节省内存。 您始终可以使用其年龄和当前日期即时对其进行计算。 * * * ## 算法效率的示例 以下是一些学习算法和数据结构使您可以执行的示例： ### 示例 1：年龄组问题 只需对[二分搜索算法](https://www.programiz.com/dsa/binary-search)进行少许修改，即可轻松解决诸如找到某个年龄段的人的问题（假设数据已排序）。 朴素的算法可以遍历所有人，然后检查它是否属于给定的年龄组，因此可以线性扩展。 而二分搜索声称自己是对数可缩放的算法。 这意味着，如果问题的大小是平方的，那么解决问题的时间只会增加一倍。 假设要花 1000 秒才能找到某个年龄段的所有人口，则需要 1 秒。然后，对于 100 万人口， * 二分搜索算法仅需 2 秒钟即可解决问题 * 朴素的算法可能需要一百万秒，大约需要 12 天 相同的二分搜索算法用于查找数字的平方根。 * * * ### 示例 2：魔方问题 想象一下，您正在编写一个程序来找到魔方的解决方案。 这个看起来很可爱的难题令人讨厌地有 43,252,003,274,489,856,000 个职位，而这些只是职位！ 想象一下，到达错误位置可以采取的路径数量。 幸运的是，解决此问题的方法可以由[图形数据结构](https://www.programiz.com/dsa/graph)表示。 有一种称为 [Dijkstra](https://www.programiz.com/dsa/dijkstra-algorithm) 的图算法可让您在线性时间内解决此问题。 是的，您没听错。 这意味着您可以在最少数量的状态下到达求解位置。 * * * ### 示例 3：DNA 问题 DNA 是携带遗传信息的分子。 它们由较小的单位组成，用罗马字母 A，C，T 和 G 表示。 想象一下自己在生物信息学领域的工作。 分配工作是找出 DNA 链中特定模式的发生。 这是计算机科学界的一个著名问题。 而且，最简单的算法所花费的时间与 ``` (number of character in DNA strand) * (number of characters in pattern) ``` 典型的 DNA 链具有数百万个此类单元。 不用担心 [**KMP 算法**](https://www.ics.uci.edu/~eppstein/161/960227.html)可以及时完成此操作，该时间与 ``` (number of character in DNA strand) + (number of characters in pattern) ``` 由`+`代替的`*`运算符进行了大量更改。 考虑到模式为 100 个字符，您的算法现在快了 100 倍。 如果您的模式包含 1000 个字符，那么 KMP 算法的速度将提高近 1000 倍。 也就是说，如果您能够在 1 秒内找到模式的出现，那么现在只需要 1 毫秒。 我们也可以用另一种方式。 您可以同时匹配 1000 条相似长度的链，而不是匹配 1 条链。 而且有无数这样的故事... * * * ## 最后的话 通常，软件开发涉及每天学习新技术。 您可以在其中一个项目中使用它们时学习大多数这些技术。 但是，算法并非如此。 如果您不太了解算法，则将无法确定是否可以优化当前正在编写的代码。 您应该事先了解它们，并在可能和重要的情况下应用它们。 我们专门讨论了算法的可扩展性。 一个软件系统由许多这样的算法组成。 优化其中任何一个都会带来更好的系统。 但是，必须注意，这并不是使系统可扩展的唯一方法。 例如，一种称为[分布式计算](https://en.wikipedia.org/wiki/Distributed_computing)的技术允许程序的独立部分同时运行到多台计算机，从而使其更具可扩展性。