递归函数的大O.

Question

我知道当你将问题集的大小分成指定的分数时,你正在处理O(log(n)).但是,当他们进行多于1次递归调用时,我很困惑.例如,在此函数中,我们将计算指数的值.

    public static long pow(long x, int n)
    {
      if(n==1)
        return x;
       if(isEven(n))
         return pow(x,n/2) * pow(x,n/2);
       else
        return pow(x*x, n/2) * x
      }

在进行分析之后,我得到的运行时间等于O(N).我对么？谢谢你的时间

Answer 1

是的，你是对的，至少在最坏情况分析下是这样。

请注意，对于n = 2^k，对于某些自然k，您会发现，除非到达停止子句，否则条件始终为真，并且递归函数将运行两次。

当这一点成立后，分析就足够了：

T(n) = T(n/2) + T(n/2) + X

其中X是某个常量（如果忽略其他递归调用，每个递归调用都需要恒定的工作量）。

根据主定理案例 1，有：

f(n) = X
a = 2, b = 2, c = 0 (since X is in O(n^0)=O(1))

由于c=0 < 1 = log_2(2)，情况 1 的条件适用，我们可以得出结论，函数T(n)在Theta(n^log_2(2)) = Theta(n)

平均情况分析：

对于平均情况，对于均匀分布的数字n，该数字的二进制表示中的一半位将向上 (1)，一半将向下 (0)。

由于除以 2 基本上是算术右移，并且isEven(n)当且仅当最低有效位为 0 时条件才成立，这意味着平均复杂度函数为：

T(n) = 0.5 T(n/2) + 0.5 * 2 T(n/2) + X = 0.5 * 3 * T(n/2)  + X 
     = 1.5 * T(n/2) + X

所以

T(n) = 3/2 T(n/2) + X

情况 1 仍然适用（假设 为常数X）：

a = 3/2，b = 2，c = 0

你会得到平均案例复杂度Theta(n^log_1.5(2))~=Theta(n^0.58)

快速说明：

这假设确实所有算术都是O(1)。如果情况并非如此（非常大的数字），您应该将它们的复杂性而不是常量放在 的定义中T(n)，然后重新分析。假设每个这样的操作都是次线性的（在数字上，而不是代表它的位），结果仍然是Theta(n)，因为主定理的情况 1 仍然适用。（对于平均情况，对于任何“更好”的函数都~O(n^0.58)不会改变显示的结果