为什么学习数据结构和算法?
- 算法和数据结构的重要性:文章解释了学习数据结构和算法对提升编程技能和在大型科技公司找到工作的重要性。
- 算法和性能优化:介绍了算法是解决问题步骤的集合,强调了优化算法对提高代码执行效率和节省资源的重要性。
- 数据结构和算法的应用:展示了数据结构和算法在解决实际问题中的作用,如提高代码的可扩展性和处理大数据量。
这篇文章适合那些刚开始学习算法并想知道这将如何提升他们的职业/编程技能的人。也适合那些想知道为什么像谷歌、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 分钟)