使用 big-O 来描述函数的最佳情况有意义吗？
Does it make sense to use big-O to describe the best case for a function?
我有一个关于大 O 表示法的非常迂腐的问题，我希望得到一些意见。我的一个单科科目说“如果他们的第一个元素相同，则最佳 O(1)”用于检查两个列表是否具有公共元素的问题。
我对此感到不安，因为它没有描述整个大输入域上的函数，而是描述具有两个具有相同第一个元素的列表的大输入的受限域。通过仅讨论函数域的子集来描述函数是否有意义？当然，当仅限于该域时，时间复杂度为 omega(1)、O(1)，因此为 theta(1)，但这并不是在描述原始函数。根据我的理解，更正确的说法是整个函数受 omega(1) 的限制。 （和 O(m*n)，其中 m、n 是两个输入列表的大小）。
大家怎么看？
讨论案例（正如您正确指出的那样，案例是函数域的子集）和这些案例中算法运行时的界限（Omega、Oh 或 Theta）是完全正确的。它是否有用是一个更难的问题，而且取决于具体情况。我通常认为 Omega-bounds 在最好的情况下，Oh-bounds 在最坏的情况下和 Theta 边界（在所有输入的“通用”情况下，当存在这样的边界时）是最“有用的”。但是，将每个集合的第一个元素相同的输入子集称为“最佳情况”似乎是合理的用法。冒泡排序的“最佳情况”是预排序数组的输入子集，并且受 O(n) 约束，优于未修改的合并排序的最佳情况范围。
从根本上说，大 O 表示法是一种讨论某些数量如何缩放的方式。在 CS 中，我们经常看到它用于谈论算法 运行 次，以至于我们忘记了以下所有都是完全合法的用例：
- 半径为r的圆面积为O(r2).
- 半径为r的球体的体积为O(r3).
- 掷n个骰子后出现2的预期数量为O(n)。
- 掷n个骰子后最少出现2的个数为O(1)。
- n对平衡括号组成的字符串的个数为O(4n).
考虑到这一点，使用大 O 表示法来讨论算法在特定情况下的行为如何扩展是完全合理的。例如，我们可以这样说：
- 用插入排序对一个包含n个已排序元素的序列进行排序所需的时间是O(n)。 （还有其他未排序的序列需要更长的时间。）
- 运行 对具有 n 个节点的树进行广度优先搜索所需的时间为 O(n)。 （在一般图中，如果边的数量更多，这可能会更大。）
- 将 n 个项目按排序顺序插入初始为空的二进制堆所需的时间为开）。 （对于反向排序的元素序列，这可以是 Θ(n log n)。）
简而言之，使用渐近符号来讨论算法的受限子情况是完全可以的。更一般地说，只要您对要量化的内容准确无误，就可以使用渐近符号来描述事物的增长方式。请参阅@Patrick87 的回答，了解更多有关在这样做时是否使用 O、Θ、Ω 等的信息。
我有一个关于大 O 表示法的非常迂腐的问题，我希望得到一些意见。我的一个单科科目说“如果他们的第一个元素相同，则最佳 O(1)”用于检查两个列表是否具有公共元素的问题。
我对此感到不安，因为它没有描述整个大输入域上的函数，而是描述具有两个具有相同第一个元素的列表的大输入的受限域。通过仅讨论函数域的子集来描述函数是否有意义？当然，当仅限于该域时，时间复杂度为 omega(1)、O(1)，因此为 theta(1)，但这并不是在描述原始函数。根据我的理解，更正确的说法是整个函数受 omega(1) 的限制。 （和 O(m*n)，其中 m、n 是两个输入列表的大小）。
大家怎么看？
讨论案例（正如您正确指出的那样，案例是函数域的子集）和这些案例中算法运行时的界限（Omega、Oh 或 Theta）是完全正确的。它是否有用是一个更难的问题，而且取决于具体情况。我通常认为 Omega-bounds 在最好的情况下，Oh-bounds 在最坏的情况下和 Theta 边界（在所有输入的“通用”情况下，当存在这样的边界时）是最“有用的”。但是，将每个集合的第一个元素相同的输入子集称为“最佳情况”似乎是合理的用法。冒泡排序的“最佳情况”是预排序数组的输入子集，并且受 O(n) 约束，优于未修改的合并排序的最佳情况范围。
从根本上说，大 O 表示法是一种讨论某些数量如何缩放的方式。在 CS 中，我们经常看到它用于谈论算法 运行 次，以至于我们忘记了以下所有都是完全合法的用例：
- 半径为r的圆面积为O(r2).
- 半径为r的球体的体积为O(r3).
- 掷n个骰子后出现2的预期数量为O(n)。
- 掷n个骰子后最少出现2的个数为O(1)。
- n对平衡括号组成的字符串的个数为O(4n).
考虑到这一点，使用大 O 表示法来讨论算法在特定情况下的行为如何扩展是完全合理的。例如，我们可以这样说：
- 用插入排序对一个包含n个已排序元素的序列进行排序所需的时间是O(n)。 （还有其他未排序的序列需要更长的时间。）
- 运行 对具有 n 个节点的树进行广度优先搜索所需的时间为 O(n)。 （在一般图中，如果边的数量更多，这可能会更大。）
- 将 n 个项目按排序顺序插入初始为空的二进制堆所需的时间为开）。 （对于反向排序的元素序列，这可以是 Θ(n log n)。）
简而言之，使用渐近符号来讨论算法的受限子情况是完全可以的。更一般地说，只要您对要量化的内容准确无误，就可以使用渐近符号来描述事物的增长方式。请参阅@Patrick87 的回答，了解更多有关在这样做时是否使用 O、Θ、Ω 等的信息。