假设我被告知算法的处理时间为Ω(n(和O(n^3(，并要求我得出结论Big-Theta是否为Θ(n^2(。我将如何回答这个问题？
f(n) = Ω(n)和f(n) = O(n^3)并不意味着f(n) = Θ(n^2)。
为了证明它的合理性，您可以考虑以下反例：
-
f(n) = n.因为对于n >= 1, n <= f(n) <= n^3来说，f(n) = Ω(n)和f(n) = O(n^3)但因为对于n >= 1, f(n) < n^2来说，f(n)不是Θ(n^2) -
f(n) = n^3.因为对于n >= 1, n <= f(n) <= n^3来说，f(n) = Ω(n)和f(n) = O(n^3)但因为对于n >= 1, f(n) > n^2来说，f(n)是不Θ(n^2)
对于给出的例子，结论是这不是一个准确的结论。换句话说，解释是，由于算法以O(n^3(为界，以Omega(n(为界，因此不能仅根据这些条目来说明平均案例运行时间，并且需要针对多个数据集研究算法以找到平均案例时间。通常，在研究算法的最佳和最坏运行时时，如果这两者相同(意味着算法两侧受相同运行时间的限制(，则可以确定 Big-theta 是相同的运行时。否则，将需要有关算法如何使用多个数据集运行的更多信息。