时间复杂度的算法很常见O(n), O(n*log n), O(2<sup>n</sup>)等。在实践中是否有任何算法可以承受像O(n/log n), O(2^n/P(n))这样的时间复杂度？ (其中 P(n) 是 n 的多项式)？如果是这样，任何人都可以举个例子吗？如果不是，为什么这些时间复杂性在实践中很少见？谢谢。
最佳答案
在某些情况下，您确实会在实践中看到像 O(n2/log n) 这样的运行时间。有一系列技术通常被称为“Method of Four Russians”，可用于加速某些类型的算法。通常，四个俄罗斯人的技巧通过蛮力计算所有大小为 Θ(log n) 的问题的解决方案来加速算法，然后将大小为 n 或 n2 的原始输入重新构造为一组 O(n/log n) 或 O(n2/log n) 个 block ，每个 block 都是大小为 Θ(log n) 的子问题。然后，这些算法的运行时间通常是一些多项式对一些多对数项，其中多对数加速来自原始问题大小已被多对数因子缩小的事实。
例如，计算两个长度为n的字符串的编辑距离的标准DP算法运行时间为O(n2)。使用四俄罗斯式加速，这可以改进为 O(n2 / log2 n) . bool 矩阵相乘通常需要时间 O(n3)，使用原始的四俄技巧可以将其改进为 O(n3/log n)。
您可以想象类似的技巧可以为您提供像 O(2n/poly(n)) 这样的运行时间 - 只需尝试在输入呈指数级增长的输入上使用上述算法。
希望这对您有所帮助!
关于big-o - O(n/log n)、O(n^2/log n) 等时间复杂度在实践中是不是很少见？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25471906/