-1

鑑於再發生:
A(n) = A(n-1) + n*log(n)
如何查找A(n)的時間複雜度?如何解決復發A(n)= A(n-1)+ n * log(n)?

+1

我不知道這種重現關係是如何終止的。 –

+2

@LukaRahne:確實。大概A(1)是第一個任期。 – Bathsheba

+0

@Shantanu我的答案能解決你的問題嗎?你能以某種方式迴應嗎?如果需要,我願意給你更多的解釋。 – xenteros

回答

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

你看,你個續訂說:走前值,並添加nlogn它。

因此......假設A(1)= log(1)是序列的第一個元素:A(n) = SUM from i = 1 to n (ilog(i))

enter image description here

爲什麼?

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) 

解決遞歸可隨時使用時F(n) - F(n-1)是一個非遞歸函數的這種方式。在我們的情況下,它是nlogn所以它的工作。

F(n)/F(n-1)是非遞歸函數時,可以使用類似的規則。然後我們使用PI而不是SIGMA。

如果有人問我給它一個上限,我會建議嘗試以下方法:

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

所以

enter image description here

現在你有一個非常明確的上限,所以免費(O(nlog(n!)))。如果你正在尋找,你需要再花一點時間。

+0

所以A(n)= n! •日誌(n!)正確嗎? – ToxiCore

+0

不,事實並非如此。這是一筆錢。 – xenteros

+0

問題是計算遞歸關係的複雜性,而不是結果是什麼。 –

3
  1. 設A(0)= c。找到A(n)作爲n和c的函數,由sum定義。
  2. 總數有多少?
  3. 總和的最小值是多少?嘗試找到一個估計。
  4. 什麼是總和的最大值?嘗試找到一個估計。
  5. 如果你可以估計(3)和(4)使他們中的一個比其他人的常數大,你完成了嗎?爲什麼?