为什么 big-Oh 并不总是算法的最坏情况分析？
Why big-Oh is not always a worst case analysis of an algorithm?
我正在尝试学习算法分析，但我对 asymptotic notation（大 O...）和 cases（最佳、最差和平均）之间的关系感到困惑。
我了解到 Big O 符号定义了算法的上限，即它定义函数的增长不能超过其上限。
起初我觉得它是在计算最坏的情况。
我 google 关于（为什么最坏的情况不是大 O？）并得到了大量的答案，这些答案对于初学者来说并不是那么容易理解。
我总结如下：
Big O 并不总是用来表示算法的最坏情况分析，因为假设一个算法对最佳、平均和最差输入采取 O(n) 执行步骤，那么它的最佳、平均和最坏情况可以表示为 O( n).
请告诉我我是否正确，或者我遗漏了什么，因为我没有人来验证我的理解。
请提出一个更好的例子来理解为什么 Big O 并不总是 worst case.
两者不是一回事。正如其他人所说，最坏情况分析是识别算法需要最长的时间才能完成的实例（即，采取最多的步骤），然后使用它制定增长函数。可以使用 Big-Oh 或什至其他变体（例如 Big-Omega 和 Big-Theta）分析最坏情况下的时间复杂度（事实上，Big-Theta 通常是您想要的，尽管通常使用 Big-Oh 是为了简化那些不太了解理论的人的理解）。一个重要的细节以及为什么最坏情况分析有用的原因是该算法 运行 不会比它在最坏情况下的速度慢。最坏情况分析是我们在分析算法时使用的一种分析方法。
Big-Oh 本身是增长函数的渐近度量；这可以完全独立，因为人们可以使用 Big-Oh 甚至不测量算法的时间复杂度；它的起源源于数论。你说它是增长函数的渐近上限是正确的；但是您规定和构建增长函数的方式来自您的分析。如果没有上下文，增长函数的 Big-Oh 本身几乎没有意义，因为它只说明了您正在分析的函数。请记住，可以构造出无限多的具有相同时间复杂度的算法（根据 Big-Oh 的定义，Big-Oh 是一组增长函数）。
简而言之，最坏情况分析就是构建增长函数的方式，Big-Oh 符号是分析所述增长函数的一种方法。然后，我们可以将该结果与针对给定问题的竞争算法的其他最坏情况时间复杂度进行比较。如果正确完成的最坏情况分析会产生最坏情况 运行ning 时间，如果准确完成（如果使用气压计，您可以削减很多角落并仍然获得正确的渐近线），并且使用此增长函数会产生算法的最坏情况时间复杂度。 Big-Oh 本身并不能保证最坏情况下的时间复杂度，因为您必须自己制作增长函数。例如，我可以将 Big-Oh 表示法用于任何其他类型的分析（例如，最佳情况、平均情况）。这实际上取决于您要捕获的内容。例如，Big-Omega 非常适合下限。
想象一个假设的算法，在最好的情况下只需要做 1 步，在最坏的情况下需要做 n2 步，但在平均（预期）情况下，只需要做 n 步。 n 是输入大小。
对于这 3 种情况中的每一种，您都可以计算一个函数来描述该算法的时间复杂度。
1 最佳情况具有 O(1)，因为函数 f(x)=1 实际上是我们可以达到的最高值，但在这种情况下也是我们可以达到的最低值，即 omega(1)。由于 Omega 等于 O（上限和下限），我们声明此函数在最佳情况下的行为类似于 theta(1)。
2 我们可以对最坏情况进行相同的分析，并计算出 O(n2 ) = omega(n2 ) =theta(n2 )。
3 平均情况下的计数相同，但使用 theta( n )。
所以理论上你可以确定算法的 3 个案例，并为这 3 个案例计算 lower/upper/thight 边界。我希望这可以解决一些问题。
大 O 表示法显示算法如何随着输入大小增长。它没有说明哪种算法更快，因为它没有考虑到恒定的设置时间（如果输入量较小，则可能占主导地位）。所以当你说
which takes O(n) execution steps
这几乎没有任何意义。 Big O 没有说有多少执行步骤。有 C + O(n) 个步骤（其中 C 是常数），该算法根据输入大小以 n 速率增长。
大 O 可用于最佳、最差或平均情况。我们以排序为例。冒泡排序是一种朴素的 O(n^2) 排序算法，但是当列表被排序时它需要 O(n)。 Quicksort 通常用于排序（GNU 标准 C 库使用它并进行了一些修改）。 It preforms at O(n log n), however this is only true if the pivot chosen splits the array in to two equal sized pieces (on average).在最坏的情况下，我们在枢轴的一侧得到一个空数组，而 Quicksort 的执行时间为 O(n^2)。
由于 Big O 展示了算法如何随大小增长，您可以查看算法的任何方面。两次 and/or 内存使用情况的最佳情况、平均情况、最差情况。它告诉您当输入大小增加时它们如何增长 - 但它没有说明哪个更快。
如果您处理小尺寸，那么 Big O 无关紧要 - 但分析可以告诉您当输入尺寸增加时情况会怎样。
最坏情况可能不是渐近极限的一个例子：假设你有一个算法可以处理某些集合和输入之间的集合差异。它可能 运行 O(N) 时间，但随着输入变大并从工作中剔除更多值而变得更快设置。
或者，为了更抽象，f(x) = 1/x对于 x > 0 是递减的 O(1) 函数。
我将重点关注时间作为一个相当常见的兴趣项目，但 Big-O 也可用于评估内存等资源需求。您必须认识到，随着问题规模的增加，Big-O 会说明问题 scale（渐近）的运行时或资源需求。它不会 为您预测实际所需时间。预测实际运行时间需要我们知道预测公式中的常量和低阶项，它们取决于硬件、操作系统、语言、编译器等。使用 Big-O 允许我们讨论算法行为，同时回避所有那些依赖项。
让我们用几个例子来谈谈如何解释 Big-O 的可扩展性。如果一个问题的复杂度为 O(1)，则无论问题大小如何，它所花费的时间都是相同的。这可能是一纳秒或一千秒，但在极限情况下，问题大小的两倍或三倍不会改变时间。如果一个问题是 O(n)，那么将问题规模加倍或加倍将（渐近地）分别使所需时间加倍或加倍。如果一个问题是 O(n^2)，那么将问题规模加倍或增加三倍将（渐近地）分别花费 4 倍或 9 倍的时间。等等...
许多算法在最佳、平均或最坏情况下具有不同的性能。排序提供了一些相当简单的示例，说明最佳、平均和最差情况分析可能有何不同。
我假设您知道 insertion sort 的工作原理。在最坏的情况下，列表可能会倒序排列，在这种情况下，对于所有项目，每次传递都必须将当前考虑的值尽可能向左移动。这会产生 O(n^2) 行为。将列表大小加倍需要四倍的时间。更有可能的是，输入列表是随机排列的。在这种情况下，平均每个项目必须向列表的前面移动一半的距离。这比最坏的情况要少，但只是一个常数。它仍然是 O(n^2)，因此对一个比我们的第一个随机列表大两倍的随机列表进行排序平均需要四倍的时间。它会比最坏的情况更快（由于涉及常量），但它以相同的方式扩展。然而，最好的情况是列表已经排序。在这种情况下，您检查每个项目以查看是否需要将其滑向前面，并立即发现答案是 "no," 因此在检查完 n 个值中的每一个后，您就可以在 O(n) 时间内完成。因此，对两倍大小的已排序列表使用插入排序只需要两倍的时间而不是四倍的时间。
大O？
首先让我们看看Big O的正式含义：
In computer science, big O notation is used to classify algorithms
according to how their running time or space requirements grow as the
input size grows.
这意味着，Big O 表示法根据函数的增长率来表征函数：具有相同增长率的不同函数可以使用相同的 O 表示法表示。这里的O表示函数的阶数，它只提供了函数增长率的上限。
现在让我们看看Big O的规则：
- 如果f(x)是几项之和，如果有一项最大
增长率，可以保留，其他都省略
- 如果 f(x) 是几个因素的乘积，任何常数（项在
不依赖于 x) 的产品可以省略。
示例：
f(x) = 6x^4 − 2x^3 + 5
使用第一条规则，我们可以将其写为 f(x) = 6x^4
使用第二条规则，O(x^4)
什么是最坏情况？
Worst case analysis gives the maximum number of basic operations that
have to be performed during execution of the algorithm. It assumes
that the input is in the worst possible state and maximum work has to
be done to put things right.
例如，对于旨在按升序对数组进行排序的排序算法，最坏的情况发生在输入数组按降序排列时。在这种情况下，必须完成最大数量的基本操作（比较和赋值）才能按升序设置数组。
这取决于很多事情，例如：
- CPU（时间）用法
- 内存使用
- 磁盘使用
- 网络使用情况
有什么区别？
Big-O 通常用于对衡量算法最坏情况行为的函数进行陈述，但 big-O 表示法并不暗示任何此类内容。
这里的重点是我们谈论的是增长，而不是运营数量。但是，对于算法，我们确实会讨论相对于输入大小的操作数。
Big-O 用于对函数进行陈述。这些函数可以测量时间或 space 或缓存未命中或岛上的兔子或任何东西或什么都没有。 Big-O 表示法不在乎。
事实上，当用于算法时，big-O 几乎与时间无关。它是关于原始操作的。
当有人说MergeSort的时间复杂度是O(nlogn)时，他们通常指的是MergeSort进行的比较次数是O(nlogn)。这本身并没有告诉我们任何特定 MergeSort 的时间复杂度可能是多少，因为这取决于进行比较需要多少时间。换句话说，O(nlogn) 指的是比较作为原始操作。
这里很重要的一点是，当big-O应用于算法时，总是有一个底层的计算模型。 MergeSort 的时间复杂度为 O(nlogn) 的说法隐含地引用了一种计算模型，其中比较需要常数时间，其他一切都是免费的。
例子-
如果我们正在对 kk 字节长的字符串进行排序，我们可能会将“读取一个字节”视为一个原始操作，它需要常数时间，而其他一切都是免费的。
在此模型中，MergeSort 进行 O(nlogn) 次字符串比较，每次进行 O(k) 字节比较，因此时间复杂度为 O(k⋅nlogn)。 RadixSort 的一种常见实现方式是让 k 遍历 n 个字符串，每次读取一个字节，因此时间复杂度为 O(nk)。
你是对的，因为你可以肯定地说算法在最佳或平均情况下运行 O(f(n)) 时间。我们一直这样做，比如快速排序，平均为 O(N log N)，但只有 O(N^2) 最坏的情况。
但是，除非另有说明，否则当您说算法在 O(f(n)) 时间内运行时，您是说该算法在 内运行O(f(n)) 时间 在最坏的情况下 。至少它应该是这样的。有时人们会变得草率，你会经常听到哈希值 table 是 O(1)，而在最坏的情况下它实际上更糟。
大 O 定义无法表征最坏情况的另一种方式是它只是 上限。 O(N)中的任何函数在O(N^2)和[=21中也是也是 =]O(2^N)，所以我们说快速排序需要 O(2^N) 时间是完全正确的。我们只是不这么说，因为这样做没有用。
Big Theta 和 Big Omega 分别指定下界和紧界。
我正在尝试学习算法分析，但我对 asymptotic notation（大 O...）和 cases（最佳、最差和平均）之间的关系感到困惑。
我了解到 Big O 符号定义了算法的上限，即它定义函数的增长不能超过其上限。
起初我觉得它是在计算最坏的情况。 我 google 关于（为什么最坏的情况不是大 O？）并得到了大量的答案，这些答案对于初学者来说并不是那么容易理解。
我总结如下：
Big O 并不总是用来表示算法的最坏情况分析，因为假设一个算法对最佳、平均和最差输入采取 O(n) 执行步骤，那么它的最佳、平均和最坏情况可以表示为 O( n).
请告诉我我是否正确，或者我遗漏了什么，因为我没有人来验证我的理解。
请提出一个更好的例子来理解为什么 Big O 并不总是 worst case.
两者不是一回事。正如其他人所说，最坏情况分析是识别算法需要最长的时间才能完成的实例（即，采取最多的步骤），然后使用它制定增长函数。可以使用 Big-Oh 或什至其他变体（例如 Big-Omega 和 Big-Theta）分析最坏情况下的时间复杂度（事实上，Big-Theta 通常是您想要的，尽管通常使用 Big-Oh 是为了简化那些不太了解理论的人的理解）。一个重要的细节以及为什么最坏情况分析有用的原因是该算法 运行 不会比它在最坏情况下的速度慢。最坏情况分析是我们在分析算法时使用的一种分析方法。
Big-Oh 本身是增长函数的渐近度量；这可以完全独立，因为人们可以使用 Big-Oh 甚至不测量算法的时间复杂度；它的起源源于数论。你说它是增长函数的渐近上限是正确的；但是您规定和构建增长函数的方式来自您的分析。如果没有上下文，增长函数的 Big-Oh 本身几乎没有意义，因为它只说明了您正在分析的函数。请记住，可以构造出无限多的具有相同时间复杂度的算法（根据 Big-Oh 的定义，Big-Oh 是一组增长函数）。
简而言之，最坏情况分析就是构建增长函数的方式，Big-Oh 符号是分析所述增长函数的一种方法。然后，我们可以将该结果与针对给定问题的竞争算法的其他最坏情况时间复杂度进行比较。如果正确完成的最坏情况分析会产生最坏情况 运行ning 时间，如果准确完成（如果使用气压计，您可以削减很多角落并仍然获得正确的渐近线），并且使用此增长函数会产生算法的最坏情况时间复杂度。 Big-Oh 本身并不能保证最坏情况下的时间复杂度，因为您必须自己制作增长函数。例如，我可以将 Big-Oh 表示法用于任何其他类型的分析（例如，最佳情况、平均情况）。这实际上取决于您要捕获的内容。例如，Big-Omega 非常适合下限。
想象一个假设的算法，在最好的情况下只需要做 1 步，在最坏的情况下需要做 n2 步，但在平均（预期）情况下，只需要做 n 步。 n 是输入大小。 对于这 3 种情况中的每一种，您都可以计算一个函数来描述该算法的时间复杂度。 1 最佳情况具有 O(1)，因为函数 f(x)=1 实际上是我们可以达到的最高值，但在这种情况下也是我们可以达到的最低值，即 omega(1)。由于 Omega 等于 O（上限和下限），我们声明此函数在最佳情况下的行为类似于 theta(1)。 2 我们可以对最坏情况进行相同的分析，并计算出 O(n2 ) = omega(n2 ) =theta(n2 )。 3 平均情况下的计数相同，但使用 theta( n )。 所以理论上你可以确定算法的 3 个案例，并为这 3 个案例计算 lower/upper/thight 边界。我希望这可以解决一些问题。
大 O 表示法显示算法如何随着输入大小增长。它没有说明哪种算法更快，因为它没有考虑到恒定的设置时间（如果输入量较小，则可能占主导地位）。所以当你说
which takes O(n) execution steps
这几乎没有任何意义。 Big O 没有说有多少执行步骤。有 C + O(n) 个步骤（其中 C 是常数），该算法根据输入大小以 n 速率增长。
大 O 可用于最佳、最差或平均情况。我们以排序为例。冒泡排序是一种朴素的 O(n^2) 排序算法，但是当列表被排序时它需要 O(n)。 Quicksort 通常用于排序（GNU 标准 C 库使用它并进行了一些修改）。 It preforms at O(n log n), however this is only true if the pivot chosen splits the array in to two equal sized pieces (on average).在最坏的情况下，我们在枢轴的一侧得到一个空数组，而 Quicksort 的执行时间为 O(n^2)。
由于 Big O 展示了算法如何随大小增长，您可以查看算法的任何方面。两次 and/or 内存使用情况的最佳情况、平均情况、最差情况。它告诉您当输入大小增加时它们如何增长 - 但它没有说明哪个更快。
如果您处理小尺寸，那么 Big O 无关紧要 - 但分析可以告诉您当输入尺寸增加时情况会怎样。
最坏情况可能不是渐近极限的一个例子：假设你有一个算法可以处理某些集合和输入之间的集合差异。它可能 运行 O(N) 时间，但随着输入变大并从工作中剔除更多值而变得更快设置。
或者，为了更抽象，f(x) = 1/x对于 x > 0 是递减的 O(1) 函数。
我将重点关注时间作为一个相当常见的兴趣项目，但 Big-O 也可用于评估内存等资源需求。您必须认识到，随着问题规模的增加，Big-O 会说明问题 scale（渐近）的运行时或资源需求。它不会 为您预测实际所需时间。预测实际运行时间需要我们知道预测公式中的常量和低阶项，它们取决于硬件、操作系统、语言、编译器等。使用 Big-O 允许我们讨论算法行为，同时回避所有那些依赖项。
让我们用几个例子来谈谈如何解释 Big-O 的可扩展性。如果一个问题的复杂度为 O(1)，则无论问题大小如何，它所花费的时间都是相同的。这可能是一纳秒或一千秒，但在极限情况下，问题大小的两倍或三倍不会改变时间。如果一个问题是 O(n)，那么将问题规模加倍或加倍将（渐近地）分别使所需时间加倍或加倍。如果一个问题是 O(n^2)，那么将问题规模加倍或增加三倍将（渐近地）分别花费 4 倍或 9 倍的时间。等等...
许多算法在最佳、平均或最坏情况下具有不同的性能。排序提供了一些相当简单的示例，说明最佳、平均和最差情况分析可能有何不同。
我假设您知道 insertion sort 的工作原理。在最坏的情况下，列表可能会倒序排列，在这种情况下，对于所有项目，每次传递都必须将当前考虑的值尽可能向左移动。这会产生 O(n^2) 行为。将列表大小加倍需要四倍的时间。更有可能的是，输入列表是随机排列的。在这种情况下，平均每个项目必须向列表的前面移动一半的距离。这比最坏的情况要少，但只是一个常数。它仍然是 O(n^2)，因此对一个比我们的第一个随机列表大两倍的随机列表进行排序平均需要四倍的时间。它会比最坏的情况更快（由于涉及常量），但它以相同的方式扩展。然而，最好的情况是列表已经排序。在这种情况下，您检查每个项目以查看是否需要将其滑向前面，并立即发现答案是 "no," 因此在检查完 n 个值中的每一个后，您就可以在 O(n) 时间内完成。因此，对两倍大小的已排序列表使用插入排序只需要两倍的时间而不是四倍的时间。
大O？
首先让我们看看Big O的正式含义：
In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.
这意味着，Big O 表示法根据函数的增长率来表征函数：具有相同增长率的不同函数可以使用相同的 O 表示法表示。这里的O表示函数的阶数，它只提供了函数增长率的上限。
现在让我们看看Big O的规则：
- 如果f(x)是几项之和，如果有一项最大 增长率，可以保留，其他都省略
- 如果 f(x) 是几个因素的乘积，任何常数（项在 不依赖于 x) 的产品可以省略。
示例：
f(x) = 6x^4 − 2x^3 + 5
使用第一条规则，我们可以将其写为 f(x) = 6x^4
使用第二条规则，O(x^4)
什么是最坏情况？
Worst case analysis gives the maximum number of basic operations that have to be performed during execution of the algorithm. It assumes that the input is in the worst possible state and maximum work has to be done to put things right.
例如，对于旨在按升序对数组进行排序的排序算法，最坏的情况发生在输入数组按降序排列时。在这种情况下，必须完成最大数量的基本操作（比较和赋值）才能按升序设置数组。
这取决于很多事情，例如：
- CPU（时间）用法
- 内存使用
- 磁盘使用
- 网络使用情况
有什么区别？
Big-O 通常用于对衡量算法最坏情况行为的函数进行陈述，但 big-O 表示法并不暗示任何此类内容。
这里的重点是我们谈论的是增长，而不是运营数量。但是，对于算法，我们确实会讨论相对于输入大小的操作数。
Big-O 用于对函数进行陈述。这些函数可以测量时间或 space 或缓存未命中或岛上的兔子或任何东西或什么都没有。 Big-O 表示法不在乎。
事实上，当用于算法时，big-O 几乎与时间无关。它是关于原始操作的。
当有人说MergeSort的时间复杂度是O(nlogn)时，他们通常指的是MergeSort进行的比较次数是O(nlogn)。这本身并没有告诉我们任何特定 MergeSort 的时间复杂度可能是多少，因为这取决于进行比较需要多少时间。换句话说，O(nlogn) 指的是比较作为原始操作。
这里很重要的一点是，当big-O应用于算法时，总是有一个底层的计算模型。 MergeSort 的时间复杂度为 O(nlogn) 的说法隐含地引用了一种计算模型，其中比较需要常数时间，其他一切都是免费的。
例子-
如果我们正在对 kk 字节长的字符串进行排序，我们可能会将“读取一个字节”视为一个原始操作，它需要常数时间，而其他一切都是免费的。
在此模型中，MergeSort 进行 O(nlogn) 次字符串比较，每次进行 O(k) 字节比较，因此时间复杂度为 O(k⋅nlogn)。 RadixSort 的一种常见实现方式是让 k 遍历 n 个字符串，每次读取一个字节，因此时间复杂度为 O(nk)。
你是对的，因为你可以肯定地说算法在最佳或平均情况下运行 O(f(n)) 时间。我们一直这样做，比如快速排序，平均为 O(N log N)，但只有 O(N^2) 最坏的情况。
但是，除非另有说明，否则当您说算法在 O(f(n)) 时间内运行时，您是说该算法在 内运行O(f(n)) 时间 在最坏的情况下 。至少它应该是这样的。有时人们会变得草率，你会经常听到哈希值 table 是 O(1)，而在最坏的情况下它实际上更糟。
大 O 定义无法表征最坏情况的另一种方式是它只是 上限。 O(N)中的任何函数在O(N^2)和[=21中也是也是 =]O(2^N)，所以我们说快速排序需要 O(2^N) 时间是完全正确的。我们只是不这么说，因为这样做没有用。
Big Theta 和 Big Omega 分别指定下界和紧界。