algorithm - 解決方法：T（n）= T（n-1）+ n

Question

私は次のことを解決しました：

T(n) = T(n - 1) + n = O(n^2)

これを解決すると、境界が非常に緩いことがわかります。私は何か間違ったことをしましたか、それともそのようですか？

Answer 1

漸化式のベースケースも必要です。

T(1) = c
T(n) = T(n-1) + n

これを解決するには、最初に解決策を推測し、次に誘導を使用してそれが機能することを証明します。

T(n) = (n + 1) * n / 2 + c - 1

まずベースケース。n = 1の場合、必要に応じてcが得られます。

他のnの場合：

  T(n)
= (n + 1) * n / 2 + c - 1
= ((n - 1) + 2) * n / 2 + c - 1
= ((n - 1) * n / 2) + (2 * n / 2) + c - 1
= (n * (n - 1) / 2) + c - 1) + (2 * n / 2)
= T(n - 1) + n

したがって、ソリューションは機能します。

そもそも推測を得るには、c =1のときに漸化式が三角数を生成することに注意してください。

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

直感的には、三角形は正方形の約半分であり、Big-O表記では定数を無視できるため、O（n ^ 2）が期待される結果になります。

Answer 2

このように考えてください
。再帰の各「反復」で、O（n）作業を行います。
n =ベースケースになるまで、各反復にはn-1回の作業が必要です。（基本ケースはO（n）作業
であると想定しています）したがって、基本ケースがnに依存しない定数であると仮定すると、再帰のO（n）回の反復があります。
O（n）の反復がそれぞれn回ある場合、O（n）* O（n）= O（n ^ 2）です。
あなたの分析は正しいです。再帰を解決するこの方法の詳細については、再帰ツリーを調べてください。それらは他の方法と比較して非常に直感的です。

Answer 3

これの解決策は非常に簡単です。再帰を展開する必要があります。

T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = 
= T(n-3) + (n-2) + (n-1) + n = ... =
= T(0) + 1 + 2 + ... + (n-1) + n 

ここに等差数列があり、合計は1/2*n*(n-1)です。技術的には、ここで境界条件が欠落していますが、一定の境界条件を使用すると、再帰がであることがわかりますO(n^2)。

Answer 4

ほぼ正しいように見えますが、ベースケースT（1）によって異なります。T（n）からT（0）を取得するためにnステップを実行し、n項が0からnの間のどこかにあるたびに、平均n / 2であると仮定すると、n * n / 2 =（n ^ 2）/ 2 = O（n ^ 2）。