最佳情况 运行 时间：上限和下限？
Best-case running time: upper and lower bound?
在我的作业中，我以语句的形式获得了一些关于算法的信息。这些语句之一是："the best-case running time of Algorithm B is Ω(n^2);".
我的印象是算法的最佳 运行 时间总是下限、上限或紧限。我想知道这样的算法是否也可以有其最佳情况 运行 时间的上限。如果是这样，发生这种情况的算法示例有哪些？
案例 是您考虑算法性能的 class 个输入。 最佳情况 是 class 您的算法的运行时具有最理想的渐近边界的输入。通常这可能意味着没有其他 class 给出较低的 Omega 界限。 最坏的情况 是 class 的输入，您的算法的运行时对其具有最不理想的渐近界限。通常这可能意味着没有其他 class 可以提供更高的 O 界限。 平均情况 与边界的可取性无关，而是在给定输入的某些指定分布的情况下查看运行时的预期值。等等，你可以定义任何你想要的案例。
设想以下算法：
Weird(a[1...n])
if n is even then
flip a coin
if heads then bogosort(a[1...n])
else if tails then bubble_sort(a[1...n])
else if n is odd then
flip a coin
if heads then merge_sort(a[1...n])
else if tails then counting_sort(a[1...n])
给定一个包含 n 个整数的列表，每个整数都在 1 到 10 之间（含 1 和 10），此算法对列表进行排序。
在最好的情况下，n是奇数。最佳情况的下限是 Omega(n)，最佳情况的上限是 O(n log n).
最坏情况下，n是偶数。最坏情况的下限是 O(n^2)，最坏情况没有上限（因为 bogosort 可能永远不会完成，尽管这种可能性极小）。
要定义平均情况，我们需要定义概率。假设 even/odd 对于所有 n 的可能性相同，那么平均情况没有上限，平均情况的下限是 Omega(n^2)，与最坏情况相同。要为平均情况获得不同的界限，我们需要定义分布，以便 n 对于更大的列表甚至变得越来越不可能。例如，您通常传递给该算法的唯一偶数长度列表的长度可能为 2。
在我的作业中，我以语句的形式获得了一些关于算法的信息。这些语句之一是："the best-case running time of Algorithm B is Ω(n^2);".
我的印象是算法的最佳 运行 时间总是下限、上限或紧限。我想知道这样的算法是否也可以有其最佳情况 运行 时间的上限。如果是这样，发生这种情况的算法示例有哪些？
案例 是您考虑算法性能的 class 个输入。 最佳情况 是 class 您的算法的运行时具有最理想的渐近边界的输入。通常这可能意味着没有其他 class 给出较低的 Omega 界限。 最坏的情况 是 class 的输入，您的算法的运行时对其具有最不理想的渐近界限。通常这可能意味着没有其他 class 可以提供更高的 O 界限。 平均情况 与边界的可取性无关，而是在给定输入的某些指定分布的情况下查看运行时的预期值。等等，你可以定义任何你想要的案例。
设想以下算法：
Weird(a[1...n])
if n is even then
flip a coin
if heads then bogosort(a[1...n])
else if tails then bubble_sort(a[1...n])
else if n is odd then
flip a coin
if heads then merge_sort(a[1...n])
else if tails then counting_sort(a[1...n])
给定一个包含 n 个整数的列表，每个整数都在 1 到 10 之间（含 1 和 10），此算法对列表进行排序。
在最好的情况下，
n是奇数。最佳情况的下限是Omega(n)，最佳情况的上限是O(n log n).最坏情况下，
n是偶数。最坏情况的下限是O(n^2)，最坏情况没有上限（因为 bogosort 可能永远不会完成，尽管这种可能性极小）。要定义平均情况，我们需要定义概率。假设 even/odd 对于所有
n的可能性相同，那么平均情况没有上限，平均情况的下限是Omega(n^2)，与最坏情况相同。要为平均情况获得不同的界限，我们需要定义分布，以便n对于更大的列表甚至变得越来越不可能。例如，您通常传递给该算法的唯一偶数长度列表的长度可能为 2。