big-O 时间复杂度中的指数分母（分数指数）从何而来？

Question

在算法描述中，我有时会遇到这样的时间复杂度：O(n^29/20+m^7/3)。我看到 + 和幂中的分子来自哪里：+ 表示连续循环，分子表示嵌套循环。例如这个（无用的）算法有 O(n²+m) 时间复杂度：

public int compute(int n, int m) {
  int answer = 0;
  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      answer += i-j;
    }
  }
  for (int i=0; i<m; i++) {
      answer -= i;
  }
  return answer;
}

但是我不明白什么可以引入分母（第一个例子中的 20 和 3）。

Answer 1

它们来自对复杂度函数的严格分析。

一个常见的例子是Matrix Multiplication, while the Naive solution is O(n^3) multiply operations, there are some faster solutions。
最早的改进之一是使用 7（而不是 8）次乘法运算来乘以两个 2X2 矩阵。

如果您对所有子矩阵递归调用此方法，您会发现它需要 O(n^log_2(7)) ~= O(n^2.807) 次乘法。

另一个常见的例子是 Fibinacci sequence 使用 Naive 递归解决方案：

F(x) = x > 2? F(x-1) + F(x-2) : 1

虽然你可以用更宽松的界限明确地分析它并说上面是 O(2^n)，但实际上 - 更仔细的分析会告诉你你只生成 F(x) 停止子句来计算F(x) 的值。
由于我们知道F(x)在O(Phi^n)中，并且使用一些基本代数证明不停止子句的数量是停止子句数量的常数因子，我们可以推导出这个解决方案在 O(Phi^n)~=O(1.62^n) 中运行，这是一个更严格的界限。

对于实际分数，您也可以使用求根函数得到它们，其中最常见的是平方根。

例如，以下是查找数字 n 是否为质数的朴素实现：

for i from 2 to sqrt(n):
    if n % i == 0:
         return false
return true

如您所见，上面的代码运行了 O(sqrt(n)) = O(n^(1/2)) 时间。

big-O 时间复杂度中的指数分母（分数指数）从何而来？

Where do exponent denominators (fractional exponents) in big-O time complexity come from?

algorithm

big-o

time-complexity