鑑於再發生:
A(n) = A(n-1) + n*log(n)
。
如何查找A(n)
的時間複雜度?如何解決復發A(n)= A(n-1)+ n * log(n)?
-1
A
回答
6
A(n) = A(n-1) + nlog(n)
你看,你個續訂說:走前值,並添加nlogn
它。
因此......假設A(1)= log(1)是序列的第一個元素:A(n) = SUM from i = 1 to n (ilog(i))
。
爲什麼?
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) + ...
.
.
.
所以
現在你有一個非常明確的上限,所以big-o免費(O(nlog(n!))
)。如果你正在尋找big-theta,你需要再花一點時間。
3
- 設A(0)= c。找到A(n)作爲n和c的函數,由sum定義。
- 總數有多少?
- 總和的最小值是多少?嘗試找到一個估計。
- 什麼是總和的最大值?嘗試找到一個估計。
- 如果你可以估計(3)和(4)使他們中的一個比其他人的常數大,你完成了嗎?爲什麼?
相關問題
- 1. 復發:T(n)= T(n/2)+ log N
- 2. 復發T(n)= T(n - log(n))+ 1
- 3. 用a * pow(b,N)替換a * b ** N
- 4. 複製關係:T(n/16)+ n log n
- 5. 序言解析樹a^n b^n
- 6. 爲什麼是{a^n a^n | n> = 0}定期?
- 7. 如何解決:T(N)= T(N - 1)+ N
- 8. 證明log(n!)是Ω(n log(n))
- 9. 粘貼「N/A」
- 10. System.data.services.client N/A?
- 11. 是log(n!)= O((log(n))^ 2)?
- 12. Excel VBA - 解釋「N/A」值
- 13. 解決一個復發的關係T(N)= T(N-√N)+1
- 14. 問題解決復發T(n)= 4T(n/4)+ 3log n
- 15. 復發:T(n)=(2 + 1/log n)T(n/2)
- 16. 證明任何a> b> 0,b^n在Big-O a^n
- 17. Common Lisp a Lisp-n?
- 18. Excel VBA find#N/A
- 19. 這是否解決O(N log(N))時間中的3SUM?
- 20. 序言:簡單的DCG a^n b^n
- 21. 如何計算n log n = c
- 22. Javascript:將解決方案更改爲O(n log n)
- 23. 如何使用Google表格解決#N/A值= importxml函數
- 24. inplace_merge:是什麼導致N * log(N)與N-1的複雜性?
- 25. 時間複雜度O(N日誌(log n)的)+ N O(L)
- 26. f(n)= n^log(n)複雜多項式或指數
- 27. 時間複雜度 - O(n^2)到O(n log n)搜索
- 28. 構造以下語言的DFA:L = {a^n b^n | n> = 1}
- 29. 語言A = {0^n 1^n 0^n}上下文是否免費?
- 30. 主定理,解決復發,T(N)= 3T(N/2)+ nlogn
我不知道這種重現關係是如何終止的。 –
@LukaRahne:確實。大概A(1)是第一個任期。 – Bathsheba
@Shantanu我的答案能解決你的問題嗎?你能以某種方式迴應嗎?如果需要,我願意給你更多的解釋。 – xenteros