0

我正在学习 Master Theorem 的期中考试，并且遇到了 k > 0 的情况 2 的示例。我了解有关该定理的所有内容，除了常数以及它如何递增或计算。

案例 2状态：T(n) = Θ(n log b a log k+1 n) 当 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 b a = n log 2 1 = 1 --> f(n) = Θ(n log b a log 1 n)

所以跨度最终是：Θ（log 2 n）。

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

4

1 回答 1

3

您需要找到这样的参数k，以便表达式为. 在这种情况下将满足要求。为了获得所需的表达式形式，您需要进行匹配。更具体地说，它类似于求解 的方程。Θ(nlogbalogkn)Θ(log n)k=1logkn = log nk

于 2012-10-27T18:20:00.233 回答