algorithm - 主定理案例 2 - 常数 k

Question

我正在学习硕士定理的期中考试，我遇到了案例 2 的示例，其中 k > 0。除了常数及其递增或计算方式之外，我了解有关定理的所有内容。

Case 2状态:T(n) = Θ(n^log_ba log^k+1n) 当 n^{log_b a} = f(n) 但 k 从何而来？

有问题的例子:

矩阵乘法

cilk void Mult(*C, *A, *B, n) {
    float *T = Cilk_alloca(n*n*sizeof(float));
    spawn Mult(C11,A11,B11,n/2);
    spawn Mult(C12,A11,B12,n/2);
    spawn Mult(C22,A21,B12,n/2);
    spawn Mult(C21,A21,B11,n/2);
    spawn Mult(T11,A12,B21,n/2);
    spawn Mult(T12,A12,B22,n/2);
    spawn Mult(T22,A22,B22,n/2);
    spawn Mult(T21,A22,B21,n/2);
    sync;
    spawn Add(C,T,n);
    sync; 
    return;
}

cilk void Add(*C, *T, n) {
  h base case & partition matrices i
  spawn Add(C11,T11,n/2);
  spawn Add(C12,T12,n/2);
  spawn Add(C21,T21,n/2);
  spawn Add(C22,T22,n/2);
  sync;
  return;
}

求得加法的跨度为:Θ(log n)

在计算乘法跨度时，示例说明:

M1(n) = M1(n/2) + A1(n) + Θ(1)

A1(n) 是 Θ(log n) 所以真的:M1(n) = M1(n/2) + Θ(log n)

n log_ba = n log₂1 = 1 --> f(n) = Θ(n^log_ba log¹ n)

因此跨度最终为:Θ(log² n)。

我想知道为什么在这个例子中 k = 1？

Answer 1

您需要找到这样的参数k这样表达式 Θ(n<sup>log<sub>b</sub>a</sup>log<sup>k</sup>n)将是 Θ(log n) .在这种情况下 k=1将满足要求。这是您需要进行的匹配，以便获得所需的表达式形式。更具体地说，它类似于求解方程 log<sup>k</sup>n = log n对于 k .