大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,而Naive解决方案是O(n^3)多重操作,有一些更快的解决方案.
提供了使用7(而不是8)乘法运算来乘以两个2X2矩阵的第一个改进之一.

如果以递归方式为所有子矩阵调用此选项,您将看到它将需要O(n^log_2(7)) ~= O(n^2.807)乘法运算.

另一个常见的例子是使用Naive递归解的Fibinacci序列:

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

虽然你可以用更宽松的界限对它进行明确的分析,并且说上面的内容O(2^n)实际上 - 更接近的分析会告诉你,你只生成了F(x)stop子句来计算它的值F(x).
既然我们知道F(x)在O(Phi^n),并且使用一些基本代数来表明非止句子句的数量是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))及时运行.