Mon*_*onk 7 algorithm complexity-theory time-complexity data-structures
我正在尝试学习算法分析，但我陷入了asymptotic notation（大O...）和cases（最佳、最差和平均）之间的关系。
我了解到该Big O符号定义了算法的上限，即它定义函数的增长不能超过其上限。
起初，我觉得它计算的是最坏的情况。我谷歌了一下（为什么最坏的情况不是大O？）并得到了大量的答案，这些答案对于初学者来说并不那么容易理解。
我的结论如下：
Big O并不总是用来表示算法的最坏情况分析，因为，假设一个算法对最佳、平均和最差输入采取 O(n) 执行步骤，那么它的最佳、平均和最坏情况可以表示为 O （n）。
请告诉我我是否正确或者我遗漏了什么，因为我没有人来验证我的理解。请提出一个更好的例子来理解为什么Big O并不总是如此worst case。
首先让我们看看Big O正式的含义：
\n\n\n在计算机科学中，大 O 表示法用于根据运行时间或空间需求随着输入大小的增长而增长的情况对算法进行分类。
\n
这意味着，大 O 表示法根据函数的增长率来表征函数：具有相同增长率的不同函数可以使用相同的 O 表示法来表示。这里，O表示函数的阶数，它只提供一个上限函数增长率的
\n\n现在让我们看看Big O的规则：
\n\n例子：
\n\nf(x) = 6x^4 \xe2\x88\x92 2x^3 + 5
\n\n使用第一条规则，我们可以将其写为 f(x) = 6x^4
\n\n使用第二条规则，它会给我们 O(x^4)
\n\n\n\n\n最坏情况分析给出了算法执行期间必须执行的基本操作的最大数量。它假设输入处于最坏的可能状态，并且必须完成最大的工作才能纠正错误。
\n
例如，对于旨在按升序对数组进行排序的排序算法，最坏的情况发生在输入数组按降序排列时。在这种情况下，必须执行最大数量的基本操作（比较和赋值）才能按升序设置数组。
\n\n这取决于很多事情，例如：
\n\nBig-O 通常用于对衡量算法最坏情况行为的函数进行陈述，但 big-O 表示法并不暗示任何此类情况。
\n\n这里重要的一点是我们谈论的是增长，而不是运营数量。然而，对于算法，我们确实讨论相对于输入大小的操作数量。
\n\nBig-O 用于做出有关函数的陈述。这些功能可以测量时间或空间或缓存未命中或岛上的兔子或任何东西或什么都没有。Big-O 表示法不在乎\xe2\x80\x99。
\n\n事实上，当用于算法时，big-O 几乎与时间无关。它是关于原始操作的。
\n\n当有人说 MergeSort 的时间复杂度为 O(nlogn) 时，他们通常意味着 MergeSort 进行的比较次数为 O(nlogn)。这本身并没有告诉我们任何特定合并排序的时间复杂度可能是多少，因为这取决于进行比较所需的时间。换句话说，O(nlogn) 指的是比较作为原始操作。
\n\n这里重要的一点是，当big-O应用于算法时，总是有一个底层的计算模型。MergeSort 的时间复杂度为 O(nlogn) 的说法隐含地引用了一种计算模型，其中比较需要恒定的时间，而其他一切都是免费的。
\n\n例子 -
\n\n如果我们要对 kk 字节长的字符串进行排序，我们可能会将 \xe2\x80\x9cread 一个字节\xe2\x80\x9d 作为原始操作，该操作需要恒定的时间，而其他一切都是空闲的。
\n\n在此模型中，MergeSort 进行 O(nlogn) 次字符串比较，每次比较进行 O(k) 字节比较，因此时间复杂度为 O(k\xe2\x8b\x85nlogn)。RadixSort 的一种常见实现将使 k 次遍历 n 个字符串，每次读取一个字节，因此时间复杂度为 O(nk)。
\n