私はMITのオープンコースウェアのウェブサイトからいくつかのビデオ講義を見てきました。3番目の講義ビデオで、講師は再帰的行列乗算を調べ、時間計算量を考え出します。
T(n) = Θ(n3)
私は自分の数学のいくつかを本当に見直す必要があることは明らかですが、その答えとマスター定理法で言及されたケースのいずれかからの関連性は実際にはわかりません。漸化式の形式は次のとおり
T(n) = a*T(n/b) + f(n)です。n>1の場合。
この漸化式a = 8では、、、、b = 2および。f(n) = Θ(n2)
それで、彼らはどのようにして得ましたか？Θ(n3)
彼はそれを述べました、それは理にかなっています。しかし、の値を使用して、例の漸化式が3つのケースのどれに対応するかを理解することはできません。 log28 = 3f(n)
ケース2だけなので、f(n) = Θ(anything)それだけだと思います。それでも、私の問題は対数または指数の特性に関連していると思います。
もしそうなら、あなたはどのようにforを持つことからusing case 2に移行しますか？私がここで行方不明になっているのは何ですか？f(n) = Θ(nlog28 * (log2n)k+1)Θ(n3)f(n)Θ(n2)