时间复杂度如O(n/log n)、O(n^2/log n)在实践中很少见吗？

Question

时间复杂度如O(n/log n)、O(n^2/log n)在实践中很少见吗？

3

在算法中，我们通常会见到时间复杂度为O(n), O(n*log n), O(2ⁿ)等。但是，在实践中是否存在时间复杂度为O(n/log n), O(2^n/P(n))（其中P(n)是n的多项式）的算法呢？如果是这样，请问有没有示例？如果不是，那么为什么在实践中很少出现这些时间复杂度呢？谢谢。

- Weijun Zhou

4

复杂性往往会变得更加复杂。 - Hot Licks

2

任何小于O(n)的时间复杂度，例如O(n/log n)，意味着只需要读取部分输入即可回答问题。大多数有趣的问题需要阅读至少一个常数分数的输入才能回答。 - Pascal Cuoq

1

这是一个理论问题，不是编程问题。请尝试访问http://cs.stackexchange.com/。 - Raymond Chen

@PascalCuoq 您是正确的，我应该从我的问题中删除O(n/log n)。 - Weijun Zhou

刚在http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#cite_ref-7 找到一个例子，不知道是否还有其他的例子。 - Weijun Zhou

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

在某些情况下，实际上确实会看到像O(n² / log n)这样的运行时间。有一系列通常称为“四路归并算法”的技术可用于加速某些类型的算法。通常，四路归并技巧通过在所有大小为Θ(log n)的输入上强制计算问题的解决方案，然后将大小为n或n²的原始输入重新构造为 O(n / log n) 或 O(n² / log n) 块，每个块都是大小为Θ(log n)的子问题。这些算法的运行时间通常是一些多项式除以一些对数多项式项，其中对数多项式的加速来自于原始问题大小已经缩小了对数多项式因子。

例如，用于计算长度为n的两个字符串的编辑距离的标准DP算法的运行时间为O(n²)。使用类似Four-Russians的加速技巧，这可以优化到O(n²/log²n)。布尔矩阵乘法通常需要O(n³)的时间，使用原始的Four-Russians技巧可以将其优化到O(n³/log n)。

你可以想象类似的技巧，可以使你的运行时间达到O(2ⁿ/poly(n)) - 只需尝试在指数级别的大输入上使用像上面那样的算法即可。

希望这可以帮助你！