算法，时间复杂度为O(logn)和θ(logn)

Question

如果我们有两个算法。一个是O(f(x))时间复杂度，另一个是θ(f(x))时间复杂度。我们更喜欢哪一个来解决我们的问题?,为什么?

Answer 1

没有足够的信息来决定哪种算法是更好的。有可能第一种算法更可取，也有可能两种算法同样可取，甚至有可能第二种算法更可取，如果它们渐近相等，但第二种算法的常数因子更小。

1. 考虑这样一个事实，二分搜索是O(n)，因为大O只给出一个上界，而线性搜索是Θ(n)。二分搜索是更好的，因为它是渐进的更有效。
2. 考虑线性搜索，它是O(n)，并且…线性搜索，也就是Θ(n)两者都同样可取，因为它们实际上是相同的。
3. 考虑冒泡排序，它是0 (n²)，插入排序，它是Θ(n²)。插入排序平均进行~ n²/4次比较，而冒泡排序平均进行~ n²/2次比较，次数是插入排序的两倍;因此，插入排序是优选的。

所以正如你所看到的，没有更多的信息是不可能说的。

Answer 2

让我们试着比较一下算法:

第一种算法具有O(nlogn)时间复杂度，即执行时间t1为

t1 <= k1 * n * log(n) + o(n * log(n))

第二个算法是θ(nlogn)，这就是为什么

t2 = k2 * n * log(n) + o(n * log(n))

假设n足够大，所以我们可以忽略o(n * log(n))项，我们仍然有两种可能性。

1. t1 < n * log(n)
2. t1 = k1 * n * log(n)(至少对于某些最坏的情况)

在第一种情况下，对于较大的n，我们应该选择算法2，因为当n足够大时，算法1的执行时间更短。

在第二种情况下，我们必须比较未知的k1和k2，我们没有足够的信息从第一种和第二种算法中进行选择。