为什么要学习数据结构和算法？
在本文中，我们将学习为什么每个程序员都应借助示例来学习数据结构和算法。
本文适用于刚开始学习算法并想知道对提高其职业/编程技能有多大影响的人员。 对于那些想知道为什么 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 这样的网站，数百万学生可以同时观看视频，阅读答案，并且不需要更多资源。 因此，该解决方案可以解决资源紧缩下规模较大的问题。
如果您看到我们找到第一个N个自然数之和的第一个解决方案，则该解决方案不可扩展。 这是因为它要求时间随时间线性增长，而问题的大小则线性增长。 这种算法也称为线性可扩展算法。
我们的第二个解决方案具有很高的可扩展性，不需要花费更多的时间来解决更大的问题。 这些被称为恒定时间算法。
内存昂贵
内存并不总是足够可用。 在处理需要您存储或产生大量数据的代码/系统时，对于算法而言，尽可能地节省内存使用至关重要。 例如：在存储有关Person的数据时，您可以通过仅存储其age而不是出生日期来节省内存。 您始终可以使用其年龄和当前日期即时对其进行计算。
算法效率的示例
以下是一些学习算法和数据结构使您可以执行的示例：
示例 1：年龄组问题
只需对二分搜索算法进行少许修改，即可轻松解决诸如找到某个年龄段的人的问题（假设数据已排序）。
朴素的算法可以遍历所有人，然后检查它是否属于给定的年龄组，因此可以线性扩展。 而二分搜索声称自己是对数可缩放的算法。 这意味着，如果问题的大小是平方的，那么解决问题的时间只会增加一倍。
假设要花 1000 秒才能找到某个年龄段的所有人口，则需要 1 秒。然后，对于 100 万人口，
- 二分搜索算法仅需 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 毫秒。 我们也可以用另一种方式。 您可以同时匹配 1000 条相似长度的链，而不是匹配 1 条链。
而且有无数这样的故事...
最后的话
通常，软件开发涉及每天学习新技术。 您可以在其中一个项目中使用它们时学习大多数这些技术。 但是，算法并非如此。
如果您不太了解算法，则将无法确定是否可以优化当前正在编写的代码。 您应该事先了解它们，并在可能和重要的情况下应用它们。
我们专门讨论了算法的可扩展性。 一个软件系统由许多这样的算法组成。 优化其中任何一个都会带来更好的系统。
但是，必须注意，这并不是使系统可扩展的唯一方法。 例如，一种称为分布式计算的技术允许程序的独立部分同时运行到多台计算机，从而使其更具可扩展性。