特定分而治之算法的複雜性

一種算法將大小爲n的問題分解爲每個大小爲n/b的b個子問題，其中b是整數。分解的代價是n，C（1）= 1。使用重複替換顯示，對於2≥b的所有值，算法的複雜度爲O（n lg n）。（n）= C（n/b）+ n 並且在用k個步驟代替我之後得到C（n）= C（n/b^k）+ N [求和（從i = 0到k-1）的（1/b）^ I]特定分而治之算法的複雜性

K =日誌（基極b）N

我不知道我得到所有這對，因爲當我完成這個任務時，我沒有得到任何幫助，我可以幫助我弄清楚該怎麼做？

來源

2013-10-06 dood

我認爲你的再次發生是錯誤的。由於存在b個大小爲n/b的單獨子問題，因此在C（n/b）項前應該有一個b係數。復發應該是

C（1）= 1

在C（n）= B C（N/B）+ O（n）中。

使用主定理，這解決了O（n log n）。看到這另一種方式是，擴大復發k次後，我們得到

在C（n）= B ^ķ C（N/B ^ķ）+ KN

這終止當k = log _b n。插入k值並簡化會得到一個值爲O（n log n）的值。

希望這會有所幫助！

來源

2013-10-06 07:50:38 templatetypedef

將不會重複出現b^k C（n/b^k）+ b^k *（n + n/b + ... + n/b^k） – dood

或者更確切地說， C（n）= b^k * C（n/b^k）+ k * n – dood

@ user2321926-哦，哎呀，你是對的。固定！ – templatetypedef

特定分而治之算法的複雜性

回答

相關問題