冒泡排序的时间复杂度
Time Complexity of Bubble Sort
最佳情况下冒泡排序的时间复杂度解释为 O(n) 而不是 Theta(n)？这不是错的，因为最好的情况可以定义为：
最佳情况 = 最快完成时间，选择最佳输入。（例如，排序算法的最佳情况是已经排序的数据。）。
编辑：-我已经看到关于堆栈溢出和其他资源的其他问题，这些问题基于最佳 case.They 期间冒泡排序的时间复杂度，所有这些都将其解释为 O(n)，我有疑问为什么最佳情况下的时间复杂度是写成 O(n) 而不是 Theta(n)?
对于很多情况，您可以使用 O(f) 或 θ(f)。人们可以自由地将其用于最佳情况、最坏情况、平均情况或您可以定义的任何其他情况。
O(f) 表示所描述情况的渐近上限。因此，例如，您甚至可以说冒泡排序是 O(n10)——尽管这不是很有用的信息，而且人们会期望使用最大边界函数，即 O(n2) - 你也可以说在最好的情况下冒泡排序是O(n).
θ(f) 为描述的案例设置渐近上限 和下限 。所以不能一直在上下界不一样的时候使用。例如，不能说冒泡排序是 θ(n2)，也不能说它是 θ(n)：它只是没有这么紧的界限。如果您采用归并排序，则存在如此严格的界限：它的时间复杂度为 θ(nlogn)
但是，当您将冒泡排序限制为仅最佳情况时，您可以使用 Theta：冒泡排序的最佳情况是 θ(n ).
请注意，根据单词 "worst" 和 "best" 的性质，您 可以 始终使用 Theta 符号来描述相应的复杂性（至少当它已知）。另一方面，您不需要使用它。您也可以使用 O 表示法。
在实践中，人们可能经常假设 O(f) 用于算法的最坏或最佳情况，旨在给出 最低绑定可能。在那种情况下，它确实也是 θ(f).
θ(f) 也是 O(f)，但不一定相反。
最佳情况下冒泡排序的时间复杂度解释为 O(n) 而不是 Theta(n)？这不是错的，因为最好的情况可以定义为： 最佳情况 = 最快完成时间，选择最佳输入。（例如，排序算法的最佳情况是已经排序的数据。）。 编辑：-我已经看到关于堆栈溢出和其他资源的其他问题，这些问题基于最佳 case.They 期间冒泡排序的时间复杂度，所有这些都将其解释为 O(n)，我有疑问为什么最佳情况下的时间复杂度是写成 O(n) 而不是 Theta(n)?
对于很多情况，您可以使用 O(f) 或 θ(f)。人们可以自由地将其用于最佳情况、最坏情况、平均情况或您可以定义的任何其他情况。
O(f) 表示所描述情况的渐近上限。因此，例如，您甚至可以说冒泡排序是 O(n10)——尽管这不是很有用的信息，而且人们会期望使用最大边界函数，即 O(n2) - 你也可以说在最好的情况下冒泡排序是O(n).
θ(f) 为描述的案例设置渐近上限 和下限 。所以不能一直在上下界不一样的时候使用。例如，不能说冒泡排序是 θ(n2)，也不能说它是 θ(n)：它只是没有这么紧的界限。如果您采用归并排序，则存在如此严格的界限：它的时间复杂度为 θ(nlogn)
但是，当您将冒泡排序限制为仅最佳情况时，您可以使用 Theta：冒泡排序的最佳情况是 θ(n ).
请注意，根据单词 "worst" 和 "best" 的性质，您 可以 始终使用 Theta 符号来描述相应的复杂性（至少当它已知）。另一方面，您不需要使用它。您也可以使用 O 表示法。
在实践中，人们可能经常假设 O(f) 用于算法的最坏或最佳情况，旨在给出 最低绑定可能。在那种情况下，它确实也是 θ(f).
θ(f) 也是 O(f)，但不一定相反。