runtime-error - 大きなシータ実行時の複雑さを見つけるのを手伝ってくれる人はいますか

Question

私は Big Theta ( Θ ) 実行時の複雑さの概念に慣れていません。

分析する次の再帰関係があります。

T(n) = 2T(n/3) + 5n ²となり、 Θ( ² ) が得られました

T(n) = T(n/4) + n ⁴となり、 Θ(n ⁴ ) が得られました。

私の答えを確認してください。

Answer 1

あなたの答えは正しいです。この種の問題は、マスター定理を適用することで解決できます。

リンクはMaster Theoremへ、

http://en.wikipedia.org/wiki/Master_theorem#Generic_form

T(n) = a T(n/b) + f(n)の場合、a >= 1 かつ b > 1

マスター定理のケース 3 を考える必要があります。

ケース 3: f(n) = Θ(n ^c ) の場合c > log _b a

次に、T(n) = Θ(n ^c )

最初の再発

T(n) = 2T(n/3) + 5n ²

a = 2、b = 3、および f(n) = 5 n ²

したがって、f(n) = Θ(n ^c )、c = 2 です。

今 c > log _b a since 2 > log ₃ 2.

したがって、あなたが言及したように T(n) = Θ(n ² ) です。

2回目の再発

T(n) = T(n/4) + n ⁴

a = 1、b = 4、および f(n) = n ⁴

したがって、f(n) = Θ(n ^c )、c = 4 です。

今 c > log _b a since 4 > log ₄ 1.

したがって、あなたが言及したように T(n) = Θ(n ⁴ ) です。

Answer 2

これらはどちらも正しいです。各再帰方程式の第 2 項は第 1 項よりもはるかに高次であるため、第 1 項よりも優先されます (平たく言えば)。