代码之家 › 专栏 › 技术社区 › Snowman

Mergesort运行时间BigO

mergesort discrete-mathematics big-o algorithm

Snowman · 技术社区 · 15 年前

Snapes不友好的向导算法教科书声称合并的运行时间

解决方案:是的。这个说法在技术上是正确的,因为O(n^4)只给出了一个上限因为紧束缚是 Î(n log n).

我不太明白解决方案是怎么说的。O(n^4)怎么可能是正确的?

2 回复 | 直到 15 年前

Martin 15 年前

大O符号是算法运行时最坏情况的上限。

由于O(n^4)高于mergesort的最坏情况时间,因此技术上是正确的,因为它确实提供了一个界限,即mergesort的性能永远不会比O(n^4)差。

但是,这是没有帮助的,因为运行时间的更好表达式是O(n logn),这是合并排序的“最紧”限制

Chris 15 年前

更为复杂的是,big-O通常在大θ更合适的时候使用,因为大多数键盘没有θ。

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前