我正在尝试学习算法分析，但我对渐近符号(大O...)和案例(最佳、最差和平均)之间的关系感到困惑.
我了解到 Big O 符号定义了算法的上限，即它定义函数的增长不能超过其上限。
一开始我觉得它是在计算最坏的情况。 我在谷歌上搜索(为什么最坏的情况不是大 O？)并得到了大量的答案，但对于初学者来说并不是那么容易理解。
我总结如下:
Big O 并不总是用来表示算法的最坏情况分析，因为假设一个算法对最佳、平均和最差输入采取 O(n) 执行步骤，那么它的最佳、平均和最坏情况可以是表示为O(n)。
请告诉我我是否正确，或者我遗漏了什么，因为我没有人来验证我的理解。
请提出一个更好的例子来理解为什么 Big O 并不总是最坏的情况。
最佳答案
大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.
这意味着，大 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(时间)使用情况
- 内存使用情况
- 磁盘使用情况
- 网络使用情况
有什么区别？
大 O 通常用于对衡量算法最坏情况行为的函数进行陈述，但大 O 表示法并不暗示任何此类内容。
这里的重点是我们谈论的是增长，而不是运营数量。但是，对于算法，我们确实会讨论相对于输入大小的操作数。
Big-O 用于对函数进行陈述。这些功能可以测量时间或空间或缓存未命中或岛上的兔子或任何东西或什么都没有。 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)。
关于algorithm - 为什么 big-Oh 并不总是算法的最坏情况分析？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49849158/