文章
开始
开始学习
CodeGym /Java 博客 /随机的 /算法复杂度
John Squirrels
第 41 级
San Francisco

算法复杂度

已在 随机的 群组中发布
你好！今天的课程与其他课程略有不同。它的不同之处在于它仅与 Java 间接相关。 算法复杂度 - 1 也就是说，这个主题对每个程序员都非常重要。我们将讨论算法。什么是算法？简而言之，它是为达到预期结果而必须完成的一些动作序列。我们在日常生活中经常使用算法。例如，每天早上您都有一项特定任务：去上学或上班，同时：
  • 穿着衣服
  • 干净的
  • 美联储
什么算法可以让你达到这个结果？
  1. 使用闹钟叫醒。
  2. 冲个澡，把自己洗干净。
  3. 做早餐和一些咖啡或茶。
  4. 吃。
  5. 如果你前一天晚上没有熨衣服，那就熨吧。
  6. 穿上衣服。
  7. 离开这房子。
这一系列动作绝对会让你得到想要的结果。在编程中，我们不断努力以完成任务。这些任务的很大一部分可以使用已知的算法来执行。例如，假设您的任务是：对数组中 100 个姓名的列表进行排序。这个任务很简单，但是可以用不同的方法来解决。这是一种可能的解决方案： 按字母顺序对名称进行排序的算法：
  1. 购买或下载 1961 年版的韦氏第三版新国际词典。
  2. 在这本词典中找到我们列表中的每个名字。
  3. 在一张纸上，写下名字所在的字典页码。
  4. 用纸片对名字进行排序。
这样的一系列动作能完成我们的任务吗？是的，它肯定会。这个解决方案有效吗？几乎不。这里我们谈到算法的另一个非常重要的方面：它们的效率。有几种方法可以完成此任务。但是无论是在编程中还是在日常生活中，我们都希望选择效率最高的方式。如果您的任务是制作一块涂了黄油的吐司，您可以先播种小麦并给牛挤奶。但那将是一个低效的解决方案——这将花费大量时间并花费大量资金。您只需购买面包和黄油即可完成简单的任务。虽然它确实可以让您解决问题，但涉及小麦和奶牛的算法太复杂而无法在实践中使用。在编程中，我们有一种称为大 O 符号的特殊符号来评估算法的复杂性。 Big O 可以评估算法的执行时间在多大程度上取决于输入数据的大小。让我们看一个最简单的例子：数据传输。想象一下，您需要以文件的形式远距离（例如 5000 英里）发送一些信息。什么算法最有效？这取决于您正在使用的数据。例如，假设我们有一个 10 MB 的音频文件。 算法复杂度 - 2在这种情况下，最有效的算法是通过 Internet 发送文件。不会超过几分钟！让我们重述一下我们的算法： “如果你想在 5000 英里的距离内以文件形式传输信息，你应该通过 Internet 发送数据”。 出色的。现在我们来分析一下。 它完成我们的任务了吗？嗯，是的，确实如此。但是关于它的复杂性我们能说什么呢？嗯，现在事情变得越来越有趣了。事实上，我们的算法非常依赖于输入数据，即文件的大小。如果我们有 10 兆字节，那么一切都很好。但是如果我们需要发送 500 兆字节呢？20GB？500TB？30 PB？我们的算法会停止工作吗？不，确实可以传输所有这些数据量。 会花更长的时间吗？是的，它会的！现在我们知道了我们算法的一个重要特征：发送的数据量越大，运行算法所需的时间就越长. 但我们希望更准确地了解这种关系（输入数据大小与发送所需时间之间的关系）。在我们的例子中，算法复杂度是线性的。“线性”意味着随着输入数据量的增加，发送它所花费的时间将大致成比例地增加。如果数据量翻倍，那么发送它所需的时间也会翻倍。如果数据增加10倍，那么传输时间就会增加10倍。使用大 O 表示法，我们算法的复杂度表示为O(n). 你应该记住这个符号以备将来使用——它总是用于具有线性复杂度的算法。请注意，我们在这里不是在谈论可能会有所不同的几件事：互联网速度、我们计算机的计算能力等等。在评估算法的复杂性时，考虑这些因素根本没有意义——无论如何，它们不在我们的控制范围内。大 O 符号表示算法本身的复杂性，而不是它运行的“环境”。 让我们继续我们的例子。假设我们最终了解到我们需要发送总计 800 TB 的文件。当然，我们可以通过 Internet 发送它们来完成我们的任务。只有一个问题：以标准的家庭数据传输速率（每秒 100 兆位），大约需要 708 天。 快2年了！:O 我们的算法显然不适合这里。我们需要一些其他的解决方案！没想到，IT巨头亚马逊来救我们了！亚马逊的 Snowmobile 服务让我们可以将大量数据上传到移动存储，然后通过卡车将其运送到所需地址！ 算法复杂度 - 3所以，我们有一个新的算法！ “如果你想在 5000 英里的距离内以文件的形式传输信息，并且这样做需要超过 14 天才能通过互联网发送，你应该用亚马逊卡车发送数据。” 我们在这里随意选择了14天。假设这是我们可以等待的最长期限。让我们分析一下我们的算法。它的速度怎么样？即使卡车仅以 50 英里/小时的速度行驶，它也能在 100 小时内行驶 5000 英里。这才四天多一点！这比通过 Internet 发送数据的选择要好得多。这个算法的复杂度如何？它也是线性的，即O(n)吗？不它不是。毕竟，卡车不在乎你装载它的重量——它仍然会以大致相同的速度行驶并准时到达。无论我们有 800 TB 还是 10 倍，卡车仍将在 5 天内到达目的地。换句话说，基于卡车的数据传输算法具有恒定的复杂度. 这里，“恒定”意味着它不依赖于输入数据的大小。在卡车上放一个 1GB 的闪存盘，它会在 5 天内到达。放入包含 800 TB 数据的磁盘，它会在 5 天内到达。使用大 O 表示法时，常数复杂度由O(1)表示。我们已经熟悉了O(n)和O(1)，所以现在让我们看一下编程世界中的更多示例 :) 假设给定一个包含 100 个数字的数组，任务是将每个数字显示在控制台。for您编写一个执行此任务的 普通循环
Java webinar 

int[] numbers = new int[100];
// ...fill the array with numbers

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)，即复杂度不变。为什么？请注意，我们在列表的开头插入了每个数字。此外，您会记得，当您向 a 中插入一个数字时LinkedList，元素不会移动到任何地方。链接（或引用）已更新（如果您忘记了 LinkedList 的工作原理，请查看我们的旧课程之一）。如果我们列表中的第一个数字是x，并且我们在列表的前面插入数字 y ，那么我们需要做的就是： 

x.previous  = y;
y.previous = null;
y.next = x;
当我们更新链接时，我们不关心 中已经有多少数字LinkedList，无论是一还是十亿。算法的复杂度是常数，即O(1)。

对数复杂度

不要恐慌！:) 如果“对数”这个词让您想结束本课并停止阅读，请坚持几分钟。这里不会有任何疯狂的数学（在其他地方有很多类似的解释），我们将挑选每个例子。想象一下，您的任务是在 100 个数字的数组中找到一个特定的数字。更准确地说，您需要检查它是否存在。一旦找到所需的数字，搜索就会结束，您会在控制台中显示以下内容：“找到所需的数字！它在数组中的索引 = ...”。您将如何完成此任务？这里的解决方案很明显：您需要一个一个地遍历数组的元素，从第一个（或最后一个）开始，并检查当前数字是否与您要查找的数字匹配。因此，动作的数量直接取决于数组中元素的数量。如果我们有 100 个数字，那么我们可能需要转到下一个元素 100 次并执行 100 次比较。如果有 1000 个数字，那么可能会有 1000 次比较。这显然是线性复杂度，即O(n)。现在我们将对我们的示例添加一个改进：您需要查找数字的数组按升序排序。这对我们的任务有什么改变吗？我们仍然可以对所需的数字执行暴力搜索。但或者，我们可以使用众所周知的二进制搜索算法。 算法复杂度 - 5在图像的顶行，我们看到一个排序数组。我们需要找到其中的数字 23。我们没有遍历数字，而是简单地将数组分成两部分并检查数组中的中间数字。找到位于单元格 4 中的数字并检查它（图像中的第二行）。这个数字是 16，我们正在寻找 23。当前的数字小于我们正在寻找的数字。这意味着什么？代表着不需要检查所有前面的数字（位于数字 16 之前的数字）：它们保证小于我们要查找的数字，因为我们的数组已排序！我们继续在剩余的 5 个元素中搜索。 笔记：我们只进行了一次比较，但我们已经排除了一半的可能选项。我们只剩下 5 个元素。我们将重复我们之前的步骤，再次将剩余的子数组分成两半，并再次取中间元素（图像中的第 3 行）。这个数字是 56，它比我们要找的那个大。这意味着什么？这意味着我们已经排除了另外 3 种可能性：数字 56 本身以及它后面的两个数字（因为它们保证大于 23，因为数组已排序）。我们只剩下 2 个数字要检查（图像中的最后一行）——数组索引为 5 和 6 的数字。我们检查其中的第一个，然后找到我们要找的东西——数字 23！它的指数是5！让我们看看我们的算法的结果，然后我们' 我们将分析其复杂性。顺便说一下，现在你明白为什么这被称为二分查找了：它依赖于重复地将数据分成两半。结果令人印象深刻！如果我们使用线性搜索来寻找数字，我们将需要多达 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）。 二分搜索算法的复杂度是对数的，或者，如果我们使用大 O 表示法，则为O(log n). 为什么叫它？对数就像求幂的反面。二进制对数是数字 2 必须提高到的幂才能获得一个数字。例如，我们有 10,000 个元素需要使用二分查找算法进行查找。 算法复杂度 - 6目前，您可以查看值表就知道这样做最多需要 14 次比较。但是，如果没有人提供这样的表格并且您需要计算确切的最大比较次数怎么办？你只需要回答一个简单的问题：你需要将数字 2 提高到多少次方才能使结果大于或等于要检查的元素数？ 对于 10,000，它是 14 次方。2的13次方太小了（8192），但是2的14次方=16384，并且这个数字满足我们的条件（它大于或等于数组中元素的数量）。我们找到了对数：14。这就是我们可能需要的比较次数！:) 算法和算法的复杂性是一个太宽泛的话题，一节课都讲不完。但知道这一点非常重要：许多求职面试都会涉及涉及算法的问题。对于理论，我可以为您推荐一些书籍。您可以从“ Grokking 算法”开始。本书中的示例是用 Python 编写的，但本书使用的语言和示例非常简单。这是初学者的最佳选择，而且，它不是很大。在更严肃的阅读中，我们有Robert Lafore和Robert Sedgewick的书. 两者都是用 Java 编写的，这将使您的学习更容易一些。毕竟，您对这门语言相当熟悉！:) 对于具有良好数学技能的学生，最好的选择是Thomas Cormen 的书。但是光靠理论是填不饱肚子的！ 知识！=能力。您可以在HackerRank和LeetCode上练习解决涉及算法的问题。这些网站的任务甚至在谷歌和 Facebook 的面试中也经常使用，所以你绝对不会觉得无聊:) 为了强化本课程材料，我建议你在 YouTube 上观看这个关于大 O 符号的优秀视频。下节课见！:)
Java university
评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION