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

> 原文： [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）感到欣喜若狂，他们几乎可以在短时间内建立自己的东西。 让我们潜入他们的工作区，听听他们的谈话。

```
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 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`个自然数之和的第一个解决方案，则该解决方案不可扩展。 这是因为它要求时间随时间线性增长，而问题的大小则线性增长。 这种算法也称为线性可伸缩算法。

我们的第二个解决方案具有很高的可扩展性，不需要花费更多的时间来解决更大的问题。 这些被称为恒定时间算法。

* * *

### 内存昂贵

内存并不总是足够可用。 在处理需要您存储或产生大量数据的代码/系统时，对于算法而言，尽可能地节省内存使用至关重要。 例如：在存储有关`人`的数据时，您可以通过仅存储其`年龄`而不是出生日期来节省内存。 您始终可以使用其年龄和当前日期即时对其进行计算。

* * *

## 算法效率的示例

以下是一些学习算法和数据结构使您可以执行的示例：

### 示例 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)的技术允许程序的独立部分同时运行到多台计算机，从而使其更具可伸缩性。