A（n）= A（n-1）+ n * log（n）？

Question

再発の場合：
A(n) = A(n-1) + n*log(n)です。
時間複雑度はどのようにしてA(n)になりますか？

Answer 1

A(n) = A(n-1) + nlog(n) 

見て、あなたのrecurenceは言う：前の値を取ると、それにnlognを追加します。

だから、A（1）= log（1）がシーケンスの最初の要素であると仮定すると：A(n) = SUM from i = 1 to n (ilog(i))です。

なぜ？ F(n) - F(n-1)が非再帰関数であるとき

A(1) = log(1). 
A(2) = log(1) + 2log(2). 
A(3) = A(2) + 3log(3) = 1log(1) + 2log(2) + 3log(3). 
. 
. 
. 
A(n) = 1log(1) + 2log(2) + 3log(3) + ... + nlog(n) 

再帰を解決するためのこの方法は、常に使用することができます。私たちの場合はnlognなので、うまくいきました。

F(n)/F(n-1)が非再帰関数である場合も同様のルールを使用できます。次に、SIGMAの代わりにPIを使用します。

私はそれに上限を与えることを求められた場合は、私は、次の試してみることをお勧め：

log(n) + log(n) + log(n) + log(n) + ... 
+   log(n-1) + log(n-1) + log(n-1) + ... 
+      log(n-2) + log(n-2) + ... 
. 
. 
. 

だから今

あなたが持っている非常に明確な上限なので、 big-oは無料です（O(nlog(n!))）。あなたがbig-thetaを探している場合は、もう少し苦労する必要があります。

Answer 2

1. A（0）= cとする。 sumで定義されるnとcの関数としてA（n）を求めます。
2. 合計でいくつの用語がありますか？
3. 合計の最小値はいくらですか？見積もりを探してみてください。
4. 合計の最大値はいくらですか？見積もりを探してみてください。
5. （3）と（4）を見積もると、それらのうちの1つが他のものよりも一定の倍になるようにすれば完了ですか？どうして？