recursion - 再発の複雑さの計算

Question

繰り返しの概念を理解するのに苦労しています。この関係の複雑さをT(n) = 2T(n/2) +1どのように計算しますか? 私はmergesortで知っています。関係はT(n) = 2T(n/2) + cnあり、各レベルで深さlog2 ^ nとcnのツリーがあることがわかります。しかし、ジェネリック関数を指定して続行する方法がわかりません。これを明確に説明できるチュートリアルはありますか?

Answer 1

あなたの再発の解は T(n) ∈ Θ(n) です。

式を展開してみましょう。

• T(n) = 2*T(n/2) + 1. (与えられた)
• T(n/2) = 2*T(n/4) + 1. (n を n/2 に置き換えます)
• T(n/4) = 2*T(n/8) + 1. (n を n/4 に置き換えます)
• T(n) = 2*(2*T(n/4) + 1) + 1 = 4*T(n/4) + 2 + 1. (代入)
• T(n) = 2*(2*(2*T(n/8) + 1) + 1) + 1 = 8*T(n/8) + 4 + 2 + 1. (代入)

そして、いくつかの観察と分析を行います。

• ^{T(n) = 2 k} * T(n/2 ^k ) + (2 ^k − 1)というパターンが現れることがわかります。
• ここで、k = log ₂ n とします。次に n = 2 ^kです。
• 代入すると、T(n) = n * T(n/n) + (n − 1) = n * T(1) + n − 1 が得られます。
• 少なくとも 1 つの n に対して、T(n) に具体的な値を与える必要があります。したがって、T(1) = 1 と仮定します。
• したがって、T(n) = n * 1 + n − 1 = 2*n − 1 であり、これは Θ(n) にあります。

資力：

• https://www.cs.duke.edu/courses/spring05/cps100/notes/slides07-4up.pdf
• http://www.cs.duke.edu/~ola/ap/recurrence.html

ただし、日常業務の場合、これらの再発を解決する通常の方法は、マスター定理を使用することです。