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

Question

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

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

今、私がこれを解決するとき、私はバウンドが非常にゆるいものであることがわかります。私は何か間違ったことをしましたか、それともまさにそのようですか？

Answer 1

このように考えてください：
再帰の各「反復」において、あなたはo（n）作業を行います。
各反復には、n =ベースケースまで、n-1作業が行われます。 （私はベースケースがO（n）作業であると仮定しています）
したがって、基本ケースがNとは独立していると仮定すると、再帰のo（n）反復があります。
o（n）がそれぞれ動作するn反復がある場合、o（n）*o（n）= o（n^2）。
分析は正しいです。再帰を解決するこの方法に関する詳細情報が必要な場合は、再帰の木を調べてください。それらは他の方法と比較して非常に直感的です。

Answer 2

また、再発関係のための基本ケースも必要です。

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 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項が平均n/2の場合、n項が0からnの間にあるので、n * n/2 =（n^2）/2 = o（n^2）。