我正在尝试学习算法分析，我被困在asymptotic notation(大O...)和cases(最佳，最差和平均)之间的关系上。
我了解到Big O符号定义了算法的上限，即它定义了函数不能超过其上限。
起初，这听起来像是因为它计算了最坏的情况。 我用谷歌搜索(为什么最坏的情况不是大O？)并得到了大量的答案，这些答案对于初学者来说并不那么容易理解。
我的结论如下：Big O并不总是用于表示算法的最坏情况分析，因为假设一个算法采用 O(n) 执行步骤进行最佳、平均和最差输入，那么它是最好的，平均和最坏的情况可以表示为 O(n)。
请告诉我我是否正确，或者我错过了一些东西，因为我没有人来验证我的理解。 请提出一个更好的例子来理解为什么Big O并不总是worst case。
Big-O？
首先让我们看看Big O正式的含义：
在计算机科学中，大O符号用于对算法进行分类 根据其运行时间或空间需求如何随着 输入大小增加。
这意味着，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)
什么是最坏情况？
最坏情况分析给出了最大数量的基本操作 必须在算法执行期间执行。它假设 输入处于最差状态，最大工作量必须 要把事情做好。
例如，对于旨在按升序对数组进行排序的排序算法，当输入数组按降序排列时，会发生最坏的情况。在这种情况下，必须执行最大数量的基本操作(比较和赋值)才能按升序设置数组。
这取决于很多事情，例如：
- 中央处理器(时间)使用情况
- 内存使用情况
- 磁盘使用情况
- 网络使用情况
有什么区别？
Big-O 通常用于对测量算法最坏情况行为的函数进行陈述，但 big-O 表示法并不意味着任何此类内容。
这里重要的一点是，我们谈论的是增长，而不是运营数量。但是，对于算法，我们确实讨论相对于输入大小的操作数。
Big-O 用于对函数进行陈述。这些函数可以测量时间或空间，或者缓存岛上的未命中或兔子，或者任何东西或什么都没有。大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)。
两者不是一回事。 正如其他人所说，最坏情况分析是识别算法需要最长才能完成的实例(即，需要最多步骤)，然后使用它制定增长函数。 人们可以使用Big-Oh，甚至其他变体(如Big-Omega和Big-Theta)来分析最坏情况的时间复杂度(事实上，Big-Theta通常是你想要的，尽管通常Big-Oh用于那些不太了解理论的人易于理解)。 一个重要的细节以及为什么最坏情况分析很有用，即算法的运行速度不会比最坏情况下慢。 最坏情况分析是我们用于分析算法的一种分析方法。
Big-Oh本身是增长函数的渐近度量;这可以完全独立，因为人们可以使用Big-Oh甚至不测量算法的时间复杂度;它的起源源于数论。 你说得对，它是增长函数的渐近上限;但是你规定和构建增长函数的方式来自你的分析。 如果没有上下文，增长函数的 Big-Oh 本身几乎没有意义，因为它只说明了您正在分析的函数。 请记住，可以构造无限多个共享相同时间复杂度的算法(根据Big-Oh的定义，Big-Oh是一组增长函数)。
简而言之，最坏情况分析是你如何构建你的增长函数，Big-Oh符号是分析所述增长函数的一种方法。 然后，我们可以将该结果与给定问题的竞争算法的其他最坏情况时间复杂性进行比较。 如果正确执行最坏情况分析，如果精确完成，则会产生最坏情况的运行时间(如果使用气压计，您可以削减很多角落，并且仍然可以获得正确的渐近)，并且使用此增长函数会产生算法的最坏情况时间复杂度。 仅靠 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 种情况计算下限/上限/大腿界限。我希望这能澄清一些问题。
https://www.google.co.in/amp/s/amp.reddit.com/r/learnprogramming/comments/3qtgsh/how_is_big_o_not_the_same_as_worst_case_or_big/
Big O 表示法显示了算法相对于输入大小的增长方式。 它没有说明哪种算法更快，因为它没有考虑恒定的设置时间(如果您的输入大小较小，这可能会占主导地位)。 所以当你说
执行步骤 O(n)
这几乎没有任何意义。 大O没有说有多少执行步骤。 有 C + O(n) 步长(其中 C 是一个常数)，并且该算法根据输入大小以 n 速率增长。
大 O 可用于最佳、最差或平均情况。 让我们以排序为例。 气泡排序是一种朴素的 O(n^2) 排序算法，但是当列表排序时，它需要 O(n)。 快速排序通常用于排序(GNU 标准 C 库使用它并进行一些修改)。它在 O(n log n 处预制)，但是仅当所选的枢轴将数组分成两个大小相等的部分(平均)时才是正确的。在最坏的情况下，我们在枢轴的一侧得到一个空数组，快速排序在 O(n^2) 处执行。
由于 Big O 显示了算法相对于大小的增长方式，因此您可以查看算法的任何方面。它的最佳情况，平均情况，时间和/或内存使用的最坏情况。 它告诉你当输入大小增长时，它们是如何增长的 - 但它没有说哪个更快。
如果您处理的是小尺寸，那么大 O 就无关紧要了 - 但分析可以告诉您当您的输入大小增加时情况如何。
最坏情况可能不是渐近极限的一个例子：假设你有一个算法，它处理某个集合和输入之间的集合差。 它可能在O(N) 时间内运行，但随着输入变大并从工作集中剔除更多值，它会变得更快。
或者，为了更抽象，x> 0 的 f(x) = 1/x是一个递减的O(1) 函数。
我将重点介绍时间作为一个相当常见的感兴趣项目，但 Big-O 也可用于评估资源需求，例如内存。 您必须意识到，Big-O 会告知问题的运行时或资源需求如何随着问题大小的增加而扩展(渐近)。 它不会为您提供所需实际时间的预测。 预测实际运行时需要我们知道预测公式中的常量和低阶项，这取决于硬件、操作系统、语言、编译器等。 使用 Big-O 可以让我们讨论算法行为，同时避开所有这些依赖关系。
让我们用几个例子来解释 Big-O 的可伸缩性。 如果问题是 O(1)，则无论问题大小如何，它都需要相同的时间。 这可能是纳秒或一千秒，但在极限下，问题的大小增加一倍或三倍不会改变时间。 如果问题是O(n)，那么将问题大小增加一倍或三倍将(渐近地)分别使所需时间增加一倍或三倍。 如果问题是 O(n^2)，那么将问题大小加倍或三倍将(渐近地)分别花费 4 倍或 9 倍的时间。 等等...
许多算法在最佳、平均或最差情况下具有不同的性能。排序提供了一些相当直接的示例，说明最佳、平均和最坏情况分析的不同之处。
我假设您知道插入排序的工作原理。 在最坏的情况下，列表可以反向排序，在这种情况下，对于所有项目，每个遍历都必须将当前考虑的值尽可能向左移动。 这会产生 O(n^2) 行为。 将列表大小加倍将需要四倍的时间。 更有可能的是，输入列表是随机顺序的。 在这种情况下，平均而言，每个项目必须向列表前面移动一半的距离。 这比最坏的情况要少，但只是一个常数。 它仍然是 O(n^2)，因此对一个比我们的第一个随机列表大两倍的随机列表进行排序，平均而言，所需的时间将增加四倍。 它将比最坏的情况更快(由于涉及的常量)，但它以相同的方式扩展。 但是，最好的情况是列表已经排序。 在这种情况下，你检查每个项目，看看它是否需要向前滑动，并立即发现答案是"否"，所以在检查每个n个值后，你在O(n)时间内完成。 因此，对大小为两倍的已排序列表使用插入排序只需要两倍而不是四倍的时间。
你是对的，因为你可以肯定地说，在最佳或平均情况下，算法在O(f(n))时间内运行。 我们一直这样做，比如说，快速排序，平均是O(N log N)，但只有O(N^2)最坏的情况。
但是，除非另有说明，否则当您说算法在O(f(n)) 时间内运行时，您是在说算法在最坏的情况下以O(f(n))时间运行。 至少应该是这样。 有时人们会变得草率，你会经常听到哈希表是O(1)，而在最坏的情况下，它实际上更糟。
大O定义无法描述最坏情况的另一种方式是，它只是一个上限。O(N) 中的任何函数也在O(N^2) 和 O(2^N) 中，因此我们说快速排序需要O(2^N)时间是完全正确的。 我们只是不这么说，因为这样做没有用。
BigTheta和Big Omega分别指定下限和紧界限。
有两个">不同"和最重要的工具：
- 最佳、最差和平均情况复杂度用于在可能的问题实例大小上生成数值函数(例如 f(x) = 2x^2 + 8x - 4)，但很难精确地使用这些函数
- 大O符号提取了要点; "算法的效率如何"，它忽略了很多不重要的东西，比如常量和......并给你一个大局