如何解決一些鐵桿重演？

我想爲我的算法類解決這些復發問題。有人可以幫助我，因爲大師定理不起作用，我無法計算從第一個樹中發生的總和，我還沒有看到第二個解決方案的好例子！如何解決一些鐵桿重演？

T（N）= 2 * T（N/3）+ N /日誌^ 2（n）的

T（N）= T（N-10）+ LOGN

2013-12-20 Saraki

這個問題似乎是題外話，因爲它不是一個具體的規劃問題，[cs.se]或[math.se]可能更合適。 – Dukeling

對不起，我是新來的，我不知道這些話題。 – Saraki

第一個例子是主定理的工作：a=2, b=3, f=n/log^2(n)。 log_b(a) < 1，所以它是第三種情況，因爲f（n）對於任何k增長（顯着）比n^(log_b(a))*log^k(n)更快。這意味着主要工作在遞歸之外完成並且T(n)=O(n/log^2(n))。

第二個例子可以解決這樣說：

T(n) 
= T(n - 10) + log(n) 
= ... 
= log(n) + log(n - 10) + ... 
= log(n * (n-10) * (n-20) * ...) 
= [n = 10k] 
= log(10^k) + log(k!) 
= k*log(10) + k*log(k) - k + O(log(k)) 
= O(k*log(k)) 
= O(n*log(n))

來源

2013-12-21 06:48:41 Abstraction

謝謝我認爲在第一種情況下，由於log^2（n），f（n）和n^{log_b a}之間存在非多項式差異，但現在我明白了事實並非如此。 – Saraki

@Saraki Trick是存在度d（比如d = 0.9），所以d> log_3（2）和n^d = o（f（n））。可以說，n ^（log_b（a））和f（n）被「劃分」了n^d。 – Abstraction

如何解決一些鐵桿重演？

回答

相關問題