問題タブ [master-theorem]

私が書いたアルゴリズムの複雑さを調べるために再帰関係を解こうとしています。これが等式..

T(n) = T(n-1) + Θ(n)

そして、O(n2) の答えを見つけましたが、それが正しかったかどうかはわかりません。誰か確認してくれませんか？

更新: 式が T(n) = T(n-1)+Θ(nlogn) の場合はどうなりますか? それでも O(n2) でしょうか?

いくつかのことを確認したかったのですが、以下の手順を実行しましたか？

ステップAで問題が発生しました。cの範囲で最終的に次のようになりました。

上限の場合はc>=1下限の場合は0<c<= 1

cn+nを組み合わせる特別な理由はありますか。その背後にあるロジックを見ることができますが、そのステップを実行する必要がありますか？それなら私はどんな場合でもそれをすることができるので...それは少し奇妙です..

次の問題を解決する方法を見つけるのに助けが
必要f(n)です: そして与えられた。 マスター定理を 試してみましたが、3 つのケースすべてがここに当てはまりませんでした。置換法を使用していると思いますが、それを適用する方法がわかりません。9f(n/3)+(n2)*(log3n)n > 1
f(1)=1
f(n)

再帰関係の式は T(n)=aT(n/b)+f(n) であることを知っています。そして、その方程式を考えると、BigO を解く方法を知っています。宿題の質問で、リスト内のノードの数をカウントする再帰関数を書くように言われました。それを実行したのに、再帰関係を書くように言われました。これが私のコードです：

しかし、私は独自の再帰関係式を作成/定式化する方法について完全に迷っています...どうすればaまたはbを見つけることができますか....どこから始めればよいかわかりません。この関数の再帰関係をどのように記述すればよいですか? ありがとうございました。

マスター メソッド - T(n) = 4*T(n/2) + (n^2)/logn を解けないのはなぜですか?

タイプ T(n) = aT(n/b) + f(n) の繰り返しを解決できることを認識しています

MIT OCW では、上記の再発は解決できないと述べています。誰かが理由について説明できますか?

次のようなケースがあるとします

これはケース 1 である必要がありますn^(1/2)>log(n)。ケース 1 にもラムダがありますf(n)=O(n^((1/2)-lambda)。これは正しいです？そして、どうすればこのラムダを見つけることができますか?

この T(n) = 2T( n/2 ) + n lg n再帰方程式のマスター定理を解くことができますか? 私は、3ree ケース条件のいずれも満たさないため、ここでマスター定理を適用できないと彼が述べているリンクから来ています。一方、彼は別の例 T(n) = 27T(n/3) + Θ(n^3 lg n) を取り上げ、閉じた解を見つけましたtheta(n^3logn) 。これを解決するために、マスター定理の 2 番目のケースを使用If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 しました。ここで、2 番目のケースに完全に適合するのに、ここで 2 番目のケースを適用できないのはなぜでしょうか。 私の考え: a = 2 , b =2; let k =1 then f(n) = theta(n^log_2 2 logn) for k= 1 so T(n) = theta(nlogn) しかし、彼がこれについて述べたように、マスター定理を適用することはできません。 .

注: これは inおよび in の f(n) bcz によるものです* * ここで間違っている場合は訂正してください。T(n) = 2T( n/2 ) + n lg n f(n) = nlog nT(n) = 27T(n/3) + Θ(n^3 lg n)f(n) = theta(n^3log n)

これはアルゴリズムの分析に関するものです。たとえば、問題の実行時間は次のとおりです。

さて、これはTHETA(log base3 n)

しかし、Master Method を使用するとTHETA(log base2 n)、Case II を使用してに評価されます。

マスターメソッドから正しい答えを得るにはどうすればよいですか?

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

ケース 2の状態: T(n) = Θ(n ^{log _b a} log ^k+1 n) when n ^{log _b a} = f(n) しかし、k はどこから来るのでしょうか?

問題の例：

行列乗算

追加のスパンは、次のようになることがわかっています: Θ(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 ₂ 1 = 1 --> f(n) = Θ(n ^{log _b a} log ¹ n)

したがって、スパンは Θ(log ² n) になります。

私が疑問に思っているのは、この例でなぜ k = 1 なのですか?

一般的な形式：T(n) = aT(n/b) + f(n)

したがって、n ^ logb（a）とf（n）を比較する必要があります

n^logba>がケース1f(n)であり、T(n)=Θ(n^logb(a))

n^logba<がケース2f(n)であり、T(n)=Θ((n^logb(a))(logb(a)))

あれは正しいですか？または私は何かを誤解しましたか？

そして、ケース3はどうですか？いつ適用されますか？