math - 再帰によって与えられた関数の正確な最悪の場合の実行時間を計算するにはどうすればよいですか?

Question

最悪の場合のランタイムがこの繰り返しによって与えられる関数の最悪の場合の実行時間の値を計算しようとしています。

T(0) = 0

T(n) = n + T(n - 1) (n > 0 の場合)

これを行う方法について誰かアドバイスはありますか？これを解決する方法がわかりません。

Answer 1

パターンを見つけるかどうかを確認するために、繰り返しを展開してみると役立つ場合があります。

• T(0) = 0
• T(1) = 1 + T(0) = 1 + 0
• T(2) = 2 + T(1) = 2 + 1 + 0
• T(3) = 3 + T(2) = 3 + 2 + 1 + 0

このパターンに基づくと、T(n) = 0 + 1 + 2 + ... + n のようになります。これはガウスが計算した有名な総和で、n(n+1)/2 になります。したがって、T(n) = n(n+1)/2 と推測できます。

これを帰納法で証明することで形式化できます。基本ケースとして、T(0) = 0 = 0(0+1)/2 なので、すべてチェックアウトします。誘導ステップの場合、T(n) = n(n+1)/2 と仮定します。次に T(n+1) = (n+1) + T(n) = (n+1) + n(n+1)/2 = (n+1) (1 + n / 2) = (n+ 1)(n+2)/2 = ((n+1))((n+1) + 1) / 2、これもチェックアウトします。

したがって、正確な値は T(n) = n(n+1)/2 です。

お役に立てれば！