algorithm - 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 ，而朴素的解决方案是 O(n^3) 乘法运算，there are some faster solutions .
最早提出的改进之一是使用 7(而不是 8)次乘法运算来将两个 2X2 矩阵相乘。

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

---

另一个常见的例子是 Fibinacci sequence使用朴素的递归解决方案:

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

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

---

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

例如，下面是一个 Naive 实现，用于查找数字 n 是否为质数:

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

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