中期的に私は問題を抱えていました：
T(n) = 8T(n/2) + n^3
そして、マスターまたは代替方法のいずれかを使用して、その大きなシータ表記を見つけることになっています。だから私がしたのは
a = 8、b = 2 k = 3
log 2 8 = 3 = k
したがって、T（n）は大きなシータn3です。私は1/3ポイントを獲得したので、間違っているに違いありません。私は何を間違えましたか？
1 に答える
3
T（n）= aT（n / b）+ f（n）
一部のe>0に対してf（n）= O（n ^（log_b（a）-e））の場合にバージョンを適用しました。
これは重要です。e>0の場合、これが真である必要があります。
f（n）= n ^ 3、b=2およびa=8の場合
n ^ 3 = O（n ^（3-e））は、e>0の場合は真ではありません。
したがって、マスター定理の間違ったバージョンを選択しました。
別のバージョンのマスター定理を適用する必要があります。
f（n）= Theta（（log n）^ k * n ^ log_b（a））for some k> = 0、
それから
T（n）= Theta（（log n）^（k + 1）* n ^ log_b（a））
あなたの問題では、このケースを適用することができ、それはT（n）= Theta（n ^ 3 log n）を与えます。
問題を解決する別の方法は次のとおりです。
T（n）= 8 T（n / 2）+ n^3。
g（n）= T（n）/ n^3とします。
それで
n ^ 3 * g（n）= 8 *（n / 2）^ 3 * g（n / 2）+ n ^ 3
つまり、g（n）= g（n / 2）+1です。
これは、g（n）= Theta（logn）であるため、T（n）= Theta（n ^ 3 logn）であることを意味します。
于 2010-06-10T04:09:24.603 に答える