問題: nサイズの問題を元のサイズの4 分の 1のサイズの6 つのサブ問題に分割するアルゴリズムがあります。分割の場合、アルゴリズムは100 ステップになり、マージの場合は75nになります。アルゴリズムの時間漸近複雑度は?
したがって、マスター定理の式は
この問題では a = 6とb = 4ですが、分割とマージの情報をどこに収めるべきかわかりません。
許容できる結果は、 O ( n 1.2924 )、オメガ( n 1.2 )、およびO (1.001 n )です。
1323 次
1 に答える
3
サブ問題を解決するたびに、現在のインスタンスをさらにサブ問題に分割する必要があります (コスト =100ステップ)。次に、サブ問題の結果をマージする必要があります (コスト =75nステップ)。
これは、(再帰のコストを除く) 1 つの部分問題を解くためのコストを表すf(n) = 75n + 100ので、ということです。f(n)
f(n) = 75n + 100ですO(n)。
したがって、あなたは見ています：T(n) = 6 * T(n/4) + O(n)
そして、次のことがわかっています。
a = 6
b = 4
f(n) = 75n + 100
次に、計算しますlog_b(a) = log_4(6) = log(6)/log(4) = 1.2924...
マスター定理のケース I を考えてみましょう。
もしf(n) = O(n^c)どこc < log_b(a)に、その後T(n) = Ө(n^(log_b(a))。
ということはわかっているf(n) = O(n^1)ので、試してみましょうc = 1。
ですかc < log_b(a)？そうですね1 < 1.2924...。
したがって、T(n) = Ө(n^(log_b(a))=> T(n) = Ө(n^1.2924...).
于 2015-06-19T00:46:00.250 に答える