algorithm - 具有 O(logn) 和 θ(logn) 时间复杂度的算法

Question

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

标签： algorithmtime-complexitybig-o

Answer 1

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

1. 考虑二进制搜索是 O(n) 的事实，因为 big-O 只给出一个上限，而线性搜索是 Θ(n)。二分搜索更可取，因为它渐近更有效。
2. 考虑线性搜索，即 O(n)，以及...线性搜索，即 Θ(n)。两者都同样可取，因为它们实际上是相同的。
3. 考虑冒泡排序，即 O(n ² ) 和插入排序，即 Θ(n ² )。插入排序平均进行 ~ n ² /4 次比较，而冒泡排序平均进行 ~ n ² /2 次比较，是两倍；所以插入排序更可取。

如您所见，没有更多信息是不可能的。