algorithm - 具有 O(logn) 和 θ(logn) 时间复杂度的算法
问题描述
如果我们有 2 个算法。其中一个是O(f(x))
时间复杂度,另一个是θ(f(x))
时间复杂度。我们更喜欢哪一个来解决我们的问题?为什么?
解决方案
没有足够的信息来决定哪种算法更可取。第一种算法可能更可取,也有可能两者同等可取,如果它们渐近相等,则第二种算法甚至可能更可取,但第二种算法的常数因子较低。
- 考虑二进制搜索是 O(n) 的事实,因为 big-O 只给出一个上限,而线性搜索是 Θ(n)。二分搜索更可取,因为它渐近更有效。
- 考虑线性搜索,即 O(n),以及...线性搜索,即 Θ(n)。两者都同样可取,因为它们实际上是相同的。
- 考虑冒泡排序,即 O(n 2 ) 和插入排序,即 Θ(n 2 )。插入排序平均进行 ~ n 2 /4 次比较,而冒泡排序平均进行 ~ n 2 /2 次比较,是两倍;所以插入排序更可取。
如您所见,没有更多信息是不可能的。
推荐阅读
- python - Python什么时候释放内存?
- javascript - 将 React 添加到网站时,如何在多个文件中使用组件?
- swift - SwiftUI 列表行没有调整以适应内容
- multithreading - 多线程应用程序中的 GDB 条件断点
- c# - c# - 通过字符串列表“循环动画”
- sql - 使用第三个表连接两个表
- javascript - 使用 lodash groupBy 以正确的方式构建数组
- maven - 即使在 jar 存在之后,也没有找到顶点 jar 异常
- python - 为什么 discord.py 不允许我添加反应?
- javascript - 如何在不显示白屏的情况下导航页面 REACT