当我遇到这个时正在阅读 CLRS:
为什么我们不忽略 a 中大 o 方程中的常数 k。 ，湾。和 c.?
最佳答案
在这种情况下，您不是在考虑单个算法的运行时间，而是在考虑由 k 参数化的系列算法的运行时间。 .考虑 k让您比较排序之间的差异 n/n == 1列表和 n/2 2 元素列表。在中间某处，有一个值 k您要为 (c) 部分计算使得 Θ(nk + n lg(n/k)) 和 Θ(n lg n) 相等。
更详细地说，插入排序是 O(n^2) 因为(粗略地说)在最坏的情况下，任何单个插入都可能花费 O(n) 时间。但是，如果子列表的长度是固定的 k，那么您知道插入步骤是 O(1)，与您排序的列表数量无关。 (即瓶颈不再在插入阶段，而是在合并阶段。)
关于algorithm - 我们应该忽略 O(nk) 中的常量 k 吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47188732/