哪里指数分母（分数指数）的大O的时间复杂度从何而来？ [英] Where do exponent denominators (fractional exponents) in big-O time complexity come from?

问题描述

在算法descirptions，我有时会遇到看起来像时间复杂度：为O（n ^20分之29 + M ^7/3 ）的。我看到 + 和权力numerators来自： + 指连续环路，并numerators意味着嵌套循环。例如，这（没用）算法的为O（n ² + M）的时间复杂度：

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）引进的分母。

But I don't understand what could introduce the denominators (20 and 3 in the first example).

推荐答案

他们从严格的分析复杂功能的到来。

They are coming from strict analysis of the complexity function.

一个常见的​​例子是矩阵乘法，而天真的解决方案是为O（n ^ 3）乘法运算，<一个href="http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication">there一些速度更快的解决方案。
一个提供给使用（而不是8）7的乘法操作，将两个2X2矩阵的第一个改进。

One common example is for Matrix Multiplication, while the Naive solution is O(n^3) multiply operations, there are some faster solutions.
One of the first improvements offered to use 7 (instead of 8) multiplications operations to multiply two 2X2 matrices.

如果你调用该递归所有的子矩阵，你会看到它需要为O（n ^ log_2（7））〜=为O（n ^ 2.807）乘法。

If you invoke this recursively for all your submatrices you will see it will require O(n^log_2(7)) ~= O(n^2.807) multiplications.

另外一个常见的​​例子是 Fibinacci序列用天真的递归解决方案：

Another common example is the Fibinacci sequence using a Naive recursive solution:

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

虽然可以definetly分析它与较为宽松的界限，说上面是 O（2 ^ n）的，其实 - 仔细分析会告诉你，你只生成 F（X）停止条款，以便计算的值F（X）。
因为我们知道F（x）是在 0（披^ N），并使用一些基本的代数证明的非停止子句的数目是一个常数因子止损条款的数量，我们可以得出，此解决方案在运行O（披^ N）〜= O（1.62 ^ n）的，这是一个更紧密的结合。

While you can definetly analyze it with more relaxed bounds and say that the above is O(2^n), in fact - closer analysis will show you that you only generate F(x) stop clauses in order to calculate the value of F(x).
Since we know F(x) is in O(Phi^n), and using some basic algebra to show that the number of non stop clauses is a constant factor of the number of stop clauses, we can derive that this solution runs in O(Phi^n)~=O(1.62^n), which is a tighter bound.

有关实际分数，你可以让他们以用root功能不错，其中最常见的是平方根。

For actual fractions, you can get them as well using root functions, where the most common is the squared root.

例如，下面是一个天真的实现找到一个数 N 是素数或不：

For example, the following is a Naive implementation to find if a number n is prime or not:

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

正如你所看到的，在上面运行 O（开方（N））=为O（n ^（1/2））的时间。

这篇关于哪里指数分母（分数指数）的大O的时间复杂度从何而来？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！