big-o - O(n/log n)、O(n^2/log n) 等时间复杂度在实践中是不是很少见？

Question

时间复杂度的算法很常见O(n), O(n*log n), O(2<sup>n</sup>)等。在实践中是否有任何算法可以承受像O(n/log n), O(2^n/P(n))这样的时间复杂度？ (其中 P(n) 是 n 的多项式)？如果是这样，任何人都可以举个例子吗？如果不是，为什么这些时间复杂性在实践中很少见？谢谢。

Answer 1

在某些情况下，您确实会在实践中看到像 O(n²/log n) 这样的运行时间。有一系列技术通常被称为“Method of Four Russians”，可用于加速某些类型的算法。通常，四个俄罗斯人的技巧通过蛮力计算所有大小为 Θ(log n) 的问题的解决方案来加速算法，然后将大小为 n 或 n² 的原始输入重新构造为一组 O(n/log n) 或 O(n²/log n) 个 block ，每个 block 都是大小为 Θ(log n) 的子问题。然后，这些算法的运行时间通常是一些多项式对一些多对数项，其中多对数加速来自原始问题大小已被多对数因子缩小的事实。

例如，计算两个长度为n的字符串的编辑距离的标准DP算法运行时间为O(n²)。使用四俄罗斯式加速，这可以改进为 O(n² / log² n) . bool 矩阵相乘通常需要时间 O(n³)，使用原始的四俄技巧可以将其改进为 O(n³/log n)。

您可以想象类似的技巧可以为您提供像 O(2ⁿ/poly(n)) 这样的运行时间 - 只需尝试在输入呈指数级增长的输入上使用上述算法。

希望这对您有所帮助!