algorithm - 递归函数的大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是一些常数，(如果忽略其他递归调用，每个递归调用需要常数的工作量)。

来自 master theorem case 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) 的函数都不会改变显示的结果