master-theorem

0熱度

1回答

void f(int n) { if (!n) return; for (int i=0; i<8; i++) f(n/12); g(n,3); } void g(int n, int i) { if (!i) return; for (int j=n; j>0; --j) { g(n,i-1); } }

0熱度

1回答

heapify堆的時間複雜度是多少

數據結構講義表明heapify的公式爲： T（n）≤T（2n/3）+Θ（1）。但是它說「通過主定理的情況2，T（n）= O（lg n），所以Heapify需要對數時間。」我真的不明白，a，b，c和d的值是什麼，爲什麼這個案例屬於定理的第二種情況，結果是O（lg n）？ THX 主定理是這裏

0熱度

2回答

如何使用主定理來計算遞歸，分而治之

我想計算Θ（） Given T (n) = T (n − 1) + n^3 我不能直接申請碩士定理規則，因爲我不知道什麼是B，所以如何導出Θ（）？

1熱度

1回答

運行時複雜性|使用碩士定理的遞歸計算

所以我遇到了一個情況，我有2個遞歸調用 - 而不是一個。我知道如何解決一個遞歸調用，但在這種情況下，我不確定我是對還是錯。我有以下問題： T（N）= T（2N/5）+ T（3N/5）+ N ，我需要找到這個最壞情況下的複雜性。（僅供參考 - 這是一種擴大的合併排序）我的感覺是使用定理中的第一個方程，但我覺得我的想法有問題。如何解決這樣的問題，任何的解釋可以理解的:)

1熱度

3回答

解決T（N）=√2* T（N/2）+登錄N使用主定理

的問題是： T(n) = √2*T(n/2) + log n 我不知道主人是否定理在這裏工作，還挺卡住。

-2熱度

1回答

解決使用主定理或擴大

我有兩個問題，我試圖但無法弄清楚。（1）（）=（ - 1）+^4 2）（）= 2（/ 2）+ lg 對於第一個，我假設替換（我是否正確？），得到kb + T （NK）。很確定這是錯的，所以需要幫助。對於第二個，我不知道在所有... 任何幫助將是巨大的！謝謝！

1熱度

1回答

當f（n）爲負時，主定理如何應用？

試圖解決這個遞歸： T(n) = 4T(n/2) + 2500 - sqrt(n) here a = 4, b=2 but my f(n) = 2500 -sqrt(n) n^ logb(a) = n^log2 (4) = n ^2 但F（N）是恆定的-sqrt（N）我的問題：我可以假設F（N）=西塔（sqrt n）還是有一些我應該知道的技巧？另外，雖然你在這裏，如果你可以解釋，如果

-2熱度

2回答

如何用主定理求解這個遞推方程T（n）=√2T（n/2）+ log n？

我知道它可以用主方法解決，但怎麼樣？請幫忙？

1熱度

2回答

複雜性算法遞歸關係

int function(int n){ if (n<=1) return 1; else return (2*function(n/2)); } 什麼是運行時間的遞歸關係T（n），爲什麼？

0熱度

1回答

主定理和指數函數

我最近遇到了關於主定理和排序的一些練習。一個要求我們找到某些表達式的Θ（）（給定T（1）=Θ（1））。大多數人與主定理解決了，但是這一次 T(n)=T(n^(5/6))+Θ(logn) 顯然不解決這樣的，因爲它不是定理的一般形式。我們如何找到它的Θ（）？