0

マスター定理の中間試験に向けて勉強していて、k > 0 のケース 2 の例に出くわしました。定数と、それがどのように増加または計算されるかを除いて、定理に関するすべてを理解しています。

ケース 2の状態: T(n) = Θ(n log b a log k+1 n) when 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 に答える