算法复杂度

你好！今天的讲座与其他讲座略有不同。它的不同之处在于它仅与 Java 间接相关。 然而，这个话题对于每个程序员来说都非常重要。我们将讨论算法。什么是算法？简单来说，这是为了达到预期结果而必须执行的一系列操作。我们在日常生活中经常使用算法。例如，每天早上您都会面临一项任务：去学校或上班，同时：

• 着装
• 干净的
• 喂养得很好

什么算法可以让你达到这个结果？

1. 被闹钟叫醒。
2. 洗澡，洗脸。
3. 准备早餐，煮咖啡/茶。
4. 吃。
5. 如果您从晚上开始就没有熨烫衣服，请熨烫它们。
6. 穿上衣服。
7. 离开这房子。

这一系列的操作肯定会让你得到想要的结果。在编程中，我们工作的全部意义就是不断解决问题。这些任务的很大一部分可以使用已知的算法来执行。例如，您面临一个任务：对数组中 100 个姓名的列表进行排序。这个问题很简单，但可以通过不同的方式解决。这是一种解决方案： 按字母顺序对名称进行排序的算法：

1. 在互联网上购买或下载《俄罗斯人名词典》1966 年版。
2. 在这本词典中查找我们列表中的每个名字。
3. 在一张纸上写下这个名字位于字典的哪一页。
4. 使用一张纸上的笔记将姓名按顺序排列。

这样一系列的行动能让我们解决我们的问题吗？是的，它将完全允许。这个解决方案会有效吗？几乎不。这里我们讨论算法的另一个非常重要的属性——它们的效率。该问题可以通过不同的方式解决。但无论是在编程还是在日常生活中，我们都会选择最有效的方法。如果您的任务是制作黄油三明治，那么您当然可以从播种小麦和挤奶开始。但这将是一个无效的解决方案——它将花费大量时间并花费大量金钱。为了解决你的简单问题，你只需购买面包和黄油即可。而小麦和牛的算法虽然可以让你解决问题，但是太复杂了，无法应用到实践中。为了评估编程中算法的复杂性，创建了一种称为Big-O（“big O”）的特殊符号。 Big-O 允许您估计算法的执行时间在多大程度上取决于传入算法的数据。让我们看一个最简单的例子——数据传输。想象一下，您需要以文件的形式远距离（例如5000公里）传输一些信息。哪种算法最有效？这取决于他必须处理的数据。例如，我们有一个 10 MB 大小的音频文件。 在这种情况下，最有效的算法是通过互联网传输文件。只需几分钟！那么，我们再次语音一下我们的算法： “如果需要在5000公里的距离上以文件的形式传输信息，就需要使用互联网上的数据传输。” 伟大的。现在我们来分析一下。 它能解决我们的问题吗？总的来说，是的，它完全解决了这个问题。但对于它的复杂性你能说些什么呢？嗯，现在事情变得有趣了。事实上，我们的算法很大程度上取决于传入的数据，即文件的大小。现在我们有 10 MB，一切都很好。如果我们需要传输500兆字节怎么办？20GB？500TB？30PB？我们的算法会停止工作吗？不，所有这些数据量仍然可以传输。 会需要更长的时间才能完成吗？是的，它会的！现在我们知道了我们算法的一个重要特征：要传输的数据量越大，算法完成所需的时间就越长。但我们想更准确地了解这种关系是什么样的（数据大小和传输数据所需的时间之间）。在我们的例子中，算法的复杂度将是线性的。“线性”是指随着数据量的增加，传输时间将大致成比例增加。如果数据量增加 2 倍，则传输时间将增加 2 倍。如果数据量增加10倍，传输时间就会增加10倍。使用 Big-O 表示法，我们的算法的复杂度定义为O(N)。最好记住此表示法以供将来参考；它始终用于具有线性复杂度的算法。请注意：我们在这里根本不是在讨论各种“可变”的事物：互联网速度、计算机的功率等等。当评估算法的复杂性时，这根本没有意义——无论如何我们都无法控制它。Big-O 评估算法本身，无论算法必须在什么“环境”中工作。 让我们继续我们的例子。假设最终要传输的文件大小为 800 TB。如果我们通过互联网传输，问题当然就解决了。只有一个问题：通过我们大多数人在家中使用的标准现代链路（每秒 100 兆比特）进行传输大约需要 708 天。 快2年了！：O 所以，我们的算法显然不适合这里。我们需要一些其他的解决方案！突然，IT巨头亚马逊来帮助我们了！其 Amazon Snowmobile 服务允许您将大量数据加载到移动存储单元中，并通过卡车将它们运送到所需的地址！ 所以我们有一个新的算法！ “如果您需要以文件形式传输信息超过5000公里的距离，并且通过互联网传输该过程需要超过14天，那么您需要使用亚马逊卡车运输。” 14 天的数字是随机选择的：假设这是我们可以承受的最长期限。让我们分析一下我们的算法。速度怎么样？即使卡车的行驶速度仅为 50 公里/小时，只需 100 小时即可行驶 5000 公里。这才四天多啊！这比互联网传输选项要好得多。这个算法的复杂度怎么样？它也是线性的，O(N)吗？不，不会的。毕竟，卡车并不关心你装载了多少东西——它仍然会以大致相同的速度行驶并准时到达。无论我们有 800 TB 还是 10 倍的数据，卡车仍将在 5 天内到达那里。换句话说，通过卡车传送数据的算法具有恒定的复杂性。“常数”意味着它不依赖于传递给算法的数据。将 1GB 闪存驱动器放在卡车上，5 天即可到达。将装有 800 TB 数据的磁盘放在那里，5 天后就会到达。使用 Big-O 时，恒定复杂度表示为O(1)。由于我们已经熟悉了O(N)和O(1)，现在让我们看更多“程序员”的例子:) 假设给你一个包含 100 个数字的数组，任务是将它们中的每一个打印到控制台。for您编写一个执行此任务的 常规循环

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

编写的算法的复杂度是多少？线性，O(N)。 程序必须执行的操作数量取决于传入其中的数字数量。如果数组中有 100 个数字，则需要执行 100 个操作（在屏幕上输出）。如果数组中有 10,000 个数字，则需要执行 10,000 个操作。我们的算法可以改进吗？不。无论如何，我们都必须对数组进行 N 次遍历并对控制台执行 N 次输出。让我们看另一个例子。

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

我们有一个空的，LinkedList可以在其中插入几个数字。我们需要估计将单个数字插入到示例中的算法的复杂性LinkedList，以及它如何依赖于列表中的元素数量。答案是O(1) - 恒定的复杂度。为什么？请注意：每次我们在列表的开头插入一个数字。此外，正如您所记得的，当将数字插入到LinkedList元素中时，它们不会移动到任何地方 - 链接被重新定义（如果您突然忘记了 LinkedList 是如何工作的，请看一下我们的旧讲座之一）。如果现在列表中的第一个数字是 number х，并且我们在列表的开头插入数字 y ，则所需要做的就是：

x.previous  = y;
y.previous = null;
y.next = x;

对于这个参考的重新定义，现在有多少个数字对我们来说并不重要LinkedList——至少一个，至少十亿。算法的复杂度是恒定的 - O(1)。

对数复杂度

不要恐慌！:) 如果“对数”这个词让您想结束讲座而不继续阅读，请等待几分钟。这里不会有数学上的困难（其他地方有很多这样的解释），我们将“在手指上”分析所有的例子。想象一下，您的任务是在 100 个数字的数组中找到一个特定的数字。更准确地说，检查它是否存在。一旦找到所需的号码，就必须停止搜索，并且控制台中应显示“已找到所需的号码！”条目。它在数组中的索引 = ....” 你会如何解决这样的问题？这里的解决方案很明显：您需要从第一个（或最后一个）开始逐个迭代数组元素，并检查当前数字是否与所需数字一致。因此，动作的数量直接取决于数组中元素的数量。如果我们有 100 个数字，那么我们需要转到下一个元素 100 次并检查数字是否匹配 100 次。如果有 1000 个数字，那么就会有 1000 个检查步骤，这显然是线性复杂度，O(N)。现在我们将为我们的示例添加一个说明：您需要在其中查找数字的数组是按升序排序的。这对我们的任务有什么改变吗？我们仍然可以通过暴力搜索来查找所需的数字。但我们可以使用众所周知的二分查找算法来代替。 在图像的第一行中，我们看到一个排序数组。在其中我们需要找到数字 23。我们只需将数组分为 2 部分并检查数组中的平均数，而不是迭代这些数字。我们找到位于单元格 4 中的数字并检查它（图中的第二行）。这个数字是16，我们正在寻找23。当前的数字更少。这是什么意思？不需要检查之前的所有数字（直到数字 16）：它们肯定会小于我们要查找的数字，因为我们的数组已排序！我们继续在剩下的 5 个元素中搜索。 注意：我们只做了一项检查，但我们已经排除了一半的可能选项。我们只剩下 5 个元素了。我们将重复我们的步骤 - 再次将剩余数组除以 2，并再次取出中间元素（图中的第 3 行）。这个数字是 56，比我们要找的要大。这是什么意思？我们丢弃另外 3 个选项 - 数字 56 本身，以及它后面的两个数字（它们肯定大于 23，因为数组已排序）。我们只剩下 2 个数字需要检查（图中的最后一行） - 数组索引为 5 和 6 的数字。我们检查其中的第一个，这就是我们要寻找的 - 数字 23！它的指数=5！让我们看看算法的结果，然后我们就会理解它的复杂性。（顺便说一句，现在你明白为什么叫二进制了：它的本质就是不断地将数据除以2）。结果令人印象深刻！如果我们使用线性搜索来查找所需的数字，我们将需要 10 次检查，但使用二分搜索我们只需 3 次即可完成！在最坏的情况下，如果最后一步我们需要的数字是第二个而不是第一个，那么将会有 4 个。它的复杂性又如何呢？这是一个非常有趣的点:) 二分搜索算法对数组中元素数量的依赖比线性搜索算法（即简单枚举）要少得多。 数组中有10 个元素时，线性搜索最多需要 10 次检查，二分搜索最多需要 4 次检查。相差2.5倍。但对于 1000 个元素的数组，线性搜索将需要 1000 次检查，而二分搜索只需要10 次！差距已经是100倍了！ 注意：数组中的元素数量增加了 100 倍（从 10 到 1000），而二分查找所需检查的数量仅增加了 2.5 倍 - 从 4 增加到 10。如果我们达到 10,000 个元素，差异就更令人印象深刻：10,000线性搜索检查，二进制检查总共 14 次。再次：元素数量增加了 1000 倍（从 10 到 10000），但检查数量仅增加了 3.5 倍（从 4 到 14）。 二分搜索算法的复杂度是对数的，或者用 Big-O 表示法是O(log n)。为什么这么叫呢？对数是指数的倒数。二进制对数用于计算 2 的幂。例如，我们需要使用二分搜索来遍历 10,000 个元素。 现在你眼前有一张图片，并且你知道这最多需要 14 次检查。但是，如果您眼前没有任何图片，并且您需要计算必要检查的确切数量，该怎么办？回答一个简单的问题就足够了：应该将数字 2 乘以多少次方才能使获得的结果 >= 正在检查的元素数量？ 10000 的 14 次方。2的13次方太小了（8192）但是2的14次方=16384，这个数字满足我们的条件（它>=数组中元素的数量）。我们找到了对数 - 14。这就是我们需要的检查次数！:) 算法及其复杂性是一个太大的话题，无法在一堂讲座中涵盖。但了解这一点非常重要：在很多面试中你都会遇到算法问题。对于理论，我可以给你推荐几本书。一个很好的起点是“ Grocking Algorithms ”：虽然书中的示例是用 Python 编写的，但本书的语言和示例非常简单。对于初学者来说是最好的选择，而且体积也很小。更严肃的阅读：罗伯特·拉弗雷（Robert Laforet）和罗伯特·塞奇威克（Robert Sedgwick）的书。两者都是用 Java 编写的，这将使您的学习变得更容易一些。毕竟，你对这门语言已经很熟悉了！:) 对于具有良好数学背景的学生来说，最好的选择是Thomas Corman 的书。但你不会仅仅满足于理论！ “知道”！=“能够” 您可以在HackerRank和Leetcode上练习解决算法问题。其中的问题甚至在 Google 和 Facebook 的面试中也经常使用，所以你绝对不会感到无聊:) 为了强化讲座材料，我建议你在 YouTube 上观看有关 Big-O 的精彩视频。下期讲座再见！:)