こんにちは、テレスコーピングによって次の再帰関係を解決しようとしていますが、最後のステップで立ち往生しています。
T(N) = T(N/2) + N T(1)=0
T(N/2) = T(N/4) + N/2
T(N/4) = T(N/8) + N/4
...
T(2) = T(1) + 2
T(N)= T(1) + N + N/2 + N/4
答えはnlognだと思いますが、上記をnlognと解釈する方法がわかりません。logn ステップを実行していることがわかりますが、n はどこから来たのでしょうか?
すべてを完全に正しく実行しましたが、合計を見つけることができませんでした。得たもの: n + n/2 + n/4 + ...、これは に等しいn * (1 + 1/2 + 1/4 + ...)。
に等しい等比級数の合計が得られました2。したがって、合計は2nです。したがって、複雑さはO(n)です。
PSこれはテレスコーピングとは呼ばれません。数学における伸縮とは、後続の項が互いに打ち消し合うことです。
答えは nlogn ではなく単に n です
T(1)=0
T(N) = T(N/2) + N
T(N/2) = T(N/4) + N/2
T(N/4) = T(N/8) + N/4 ... T(2) = T(1) + 2
テレスコピック展開には完全に log(N) 個のステートメントがあります
テレスコピックキャンセルにより、
T(N) = T(1) + N + N/2 + N/4 + N/8 +.....+ 2 があります。
T(1) = 0
T(N) = N + N/2 + ..... + 2
これは log(n) 項の幾何級数で、各項は半分になります。
T(N) = N [1 - (1/2)^log(N)] / (1/2)
T(N) = 2N[1 - 1/N]
T(N) = 2N - 2
したがって、答えは O(N) です。