Amu*_*are 12 algorithm complexity-theory
我正在学习算法分析.我理解算法运行时最差的概念.
但是,算法的最坏情况运行时间的上限和下限是多少？
有什么可以一个例子,其中一个上限用于运行算法的时间的最坏情况是从不同下界用于运行相同的算法的时间的最坏情况？
首先，我们来说说案例。\xc2\xa0算法\xc2\xa0 的\xc2\xa0输入\xc2\xa0 的情况与\xc2\ xa0问题的\xc2\xa0实例\xc2\xa0相关联。对于排序问题（我们想要按特定顺序找到集合的排列），我可以查看像数字集合 {1, 5, 4, 2, 6} 这样的实例。这组数字将是旨在解决排序问题的排序算法的输入，例如选择排序，或其他\xc2\xa0 排序算法\xc2\xa0 之一。\xc2\xa0
\n\n可以为任何想要解决问题的算法提供相同的输入集。无论我使用什么排序算法，输入集始终是相同的（因为根据定义，它们都是同一问题的实例）。然而，对于给定的算法，给定的情况可能更好或更差。无论输入是什么，某些算法总是执行相同的操作，但某些算法可能在某些输入上表现更差。然而，这意味着每个算法都有一些\xc2\xa0最佳情况\xc2\xa0和一些\xc2\xa0最坏情况；我们有时也会谈论\xc2\xa0平均情况\xc2\xa0（通过取所有情况的平均值）或\xc2\xa0预期情况\xc2\xa0（当我们有某种理由预计一种情况会更多）比其他人更常见）。
\n\n对于每个可能的输入，“找到未排序列表的最小值”的问题总是相同的。无论你编写多么聪明的算法，你都必须检查每个元素。无论您有一个零列表、一个随机数列表或一个第一个元素是最小值的列表，都没关系，直到到达末尾您才会知道。该算法的每种情况都是相同的，因此最好的情况是最坏的情况，也是平均情况和预期情况。如果列表已排序，我们可以做得更好，但这是一个不同的问题。
\n\n“在列表中查找给定元素”的问题是不同的。假设您使用的算法可以线性遍历列表，则可能会发现给定元素是列表的第一个元素，并且您立即完成。但是，它也可能是列表的最后一个元素，在这种情况下，您必须遍历整个元素才能找到它。所以你有一个最好的情况和一个最坏的情况。
\n\n当我们想要分析一个算法时，我们的算法学家会考虑我们可以向算法抛出的每一种可能的情况。通常，两个最有趣的情况是最好的情况和最坏的情况。如果将算法运行时间视为其输入的函数，则最好的情况是最小化函数的输入，最坏的情况是最大化函数的输入。我在这里使用代数数学意义上的“函数”：绘制一条线的一系列 x/y 对（输入/输出对，或在本例中为“输入大小/执行步骤数”）。
\n\n由于算法的运行时间是其输入的函数，因此对于每种可能的输入大小，我们都有不同的最佳情况（和最坏情况）。因此，有时我们将最好的情况视为单个输入，但它实际上是一组输入（每个输入大小一个）。对于给定的算法来说，最好的情况和最坏的情况是非常具体的事情。
\n\n现在边界呢？界限是我们用来与给定算法的函数进行比较的函数。我们可以考虑无数的边界函数。您可以在图表上绘制多少种可能的线条？这就是边界函数的数量。大多数算法学家通常只对少数特定函数感兴趣：例如常数函数、线性函数、对数函数、指数函数等。
\n\n上限是位于另一个函数之上的函数。下界是位于另一个函数之下的函数。当我们谈论 Big O 和 Big Omega 时，我们并不关心边界是否始终高于或低于其他函数，只是在某个点之后它们总是如此（因为有时算法对于小输入大小会变得很奇怪）。 xc2\xa0
\n\n对于任何给定函数，有无限多个可能的上限，并且对于任何给定函数，有无限多个可能的下界。但这是我们谈论不同大小的无穷大时的奇怪时刻之一。要成为上限，该函数不得低于另一个函数，因此我们排除了另一个函数以下的无限多个函数（因此它小于所有可能函数的集合）。
\n\n当然，仅仅因为有无限的上限，并不意味着它们都是有用的。函数 f(\xe2\x88\x9e) 是每个函数的上限，但这就像说“我的美元少于无限多”——对于确定我是否身无分文并不是特别有用或百万富翁。因此，我们经常对“紧”上限（也称为“最小上限”或“上界”）感兴趣，对此没有更好的上限。
\n\n我们有最好/最差的情况，代表算法运行时函数的上限和下限函数。我们有上限和下限，它们代表可能位于（分别）任何其他函数之上或之下的其他函数。它们可以结合起来阐明有关算法的关键思想。
\n\n最坏情况下界：当给该算法提供最大化算法运行时间的输入时，该函数是算法运行时函数下方的边界。
\n\n最坏情况上限：当给该算法提供最大化算法运行时间的输入时，该函数是算法运行时函数之上的边界。
\n\n最佳情况下界：当给该算法提供最小化算法运行时间的输入时，该函数是算法运行时函数下方的边界。
\n\n最佳情况上限：当给该算法提供最小化算法运行时间的输入时，该函数是算法运行时函数之上的边界。
\n\n让我们举出具体的例子来说明我们何时可能关心其中的每一个：
\n\n最坏情况下界：这里的经典示例是基于比较的排序，众所周知，在最坏情况下为 \xc2\xa0\xce\xa9(n log(n)) 。无论您设计什么算法，我都可以选择一组最坏情况的输入，其中最紧的下界函数是对数线性的。你无法制定出一种超越最坏情况限制的算法，并且你不应该费心去尝试。这是排序的地下室。当然，最坏情况有很多下界：常数、线性和次线性都是下界。但它们不是有用的下界，因为对数线性下界是最紧的下界。
\n\n最佳情况下界：插入排序的工作原理是遍历列表，并将遇到的任何无序插入到正确的位置。如果列表已排序，则只需遍历列表一次，而无需执行任何插入。这意味着最好情况的最紧下界是\xc2\xa0\xce\xa9(n)。在不牺牲正确性的情况下，您无法做得更好，因为您仍然需要能够遍历列表（线性时间）。然而，最好情况的下界比最坏情况的下界要好！
\n\n最坏情况上限：我们通常有兴趣在最坏情况下找到一个严格的上限，因为这样我们就知道我们的算法在最坏的情况下运行得有多差。插入排序的最坏情况是列表完全无序（即与其正确顺序完全相反）。每当我们看到一个新项目时，我们都必须将其移动到列表的开头，将所有后续项目向前推（这是一个线性时间操作，并且执行线性次数会导致二次行为）。然而，我们仍然知道，在最坏情况下，这种插入行为将是 O(n2)，作为最坏情况的严格上限。它不是很好，但它比指数或阶乘的上限要好！当然，这些是最坏情况下的有效上限，但同样，这不如知道二次是严格的上限那么有用。
\n\n最佳情况上限：我们的算法在最好的情况下能做的最坏的事情是什么？在之前在列表中查找元素的示例中，其中第一个元素是我们想要的元素，上限是 O(1)。在最坏的情况下，它是线性的，但在最好的情况下，可能发生的最坏情况是它仍然是恒定的。在我看来，这个特殊的想法通常不如最坏情况上限那么重要，因为我们通常更关心处理最坏的情况，而不是最好的情况。
\n\n其中一些示例实际上是\xc2\xa0\xd3\xa8，而不仅仅是O和\xc2\xa0\xce\xa9。在其他情况下，我可以选择不严格的下限或上限函数，但仍然足够近似以有用（记住，如果我们不严格，我有一个无限的井可以从中提取！） 。请注意，可能很难找到不同大小写/绑定组合的令人信服的示例，因为这些组合具有不同的效用。
\n\n您经常会看到人们对这些定义有误解。事实上，许多优秀的计算机科学家都会宽松且可互换地使用这些术语。然而，案例和界限的概念是不同的，您最好确保理解它们。这是否意味着您的日常生活中会出现这种差异？不。但是当您在几种不同的算法之间进行选择时，您需要阅读有关案例和界限的细则。有人告诉您他们的算法的最佳情况上限为 O(1) 可能是想蒙蔽您的眼睛 - 请务必询问他们最坏情况上限是什么！
\n