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

In algorithm descirptions, I sometimes encounter time complexities that look like: O(n^29/20+m^7/3). I see where + and numerators in powers come from: + means successive loops, and numerators mean nested loops. For example this (useless) algorithm has O(n²+m) time complexity:

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）。

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

一个常见的例子是矩阵乘法 http://en.wikipedia.org/wiki/Matrix_multiplication，而朴素的解决方案是O(n^3)乘法运算，有一些更快的解决方案 http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication.
第一个改进是使用 7 次（而不是 8 次）乘法运算来乘以两个 2X2 矩阵。

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

另一个常见的例子是斐波那契数列 http://en.wikipedia.org/wiki/Fibonacci_number使用朴素的递归解决方案：

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

虽然你可以用更宽松的界限来明确地分析它，并说上面是O(2^n)，事实上 - 更仔细的分析会告诉你，你只生成F(x)stop 子句以计算值F(x).
因为我们知道 F(x) 在O(Phi^n)，并使用一些基本代数来证明非停止子句的数量是停止子句数量的常数因子，我们可以得出该解决方案运行于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)) time.