runtime - これらの繰り返し関係の実行時間

Question

これらの関係の厳密な実行時間をどのように計算しますか?

• T(n)=T(n-3)+n^2
• T(n) = 4T(n/4)+log^3(n)

最初のものでは n^2 を与えたが正しくない代入法を使用し、2 つ目は Masters Theorem を使用して nlog^4(n) を得ましたが、これも正しくありませんでした。丁寧な説明助かります。ありがとう！

Answer 1

最初の再帰については、再帰ツリー法で解決できます

T(n)=T(n-3)+n^2

a) ここで、サブ問題の数が n/3 であることがわかります (i ごとに n から 3 を引くので、n/3 ステップで最後のサブ問題に到達します)。

b) 各レベルでのコストは n^2 です

したがって、時間の複雑さはおおよそ (n/3)*n^2= (n^3)/3 O(n^3) です

2番目の再帰関係に来ます

T(n)=4T(n/4)+log^3(n)

ここでは、n と log^3(n) は比較できないため、マスターの定理を適用できません nlog^3(n) のようなものがある場合、マスターの定理を適用できた多項式時間 (厳密に対数の範囲の結果)。厳密にログ時間

ここで間違っている場合は修正してください