master-theorem

3熱度

4回答

我對主定理有點新鮮，我想通過遞歸地解決尺寸爲n-1的兩個子問題並結合解決方案來解決一個尺寸爲n的問題的算法的運行時間在不斷的時間。所以公式是： T(N) = 2T(N - 1) + O(1) 但我不知道我怎麼能制定主定理的條件。我的意思是我們沒有在這種情況下，主定理公式的bb=N/(N-1)？如果是，因爲明顯a > b^k自k=0並且是O(N^z)其中z=log2與(N/N-1)的基數我

1熱度

1回答

遞推關係的運行時

剛把此上測驗：T（N）= 4T（SQRT（n））的+ 5 我簡化它使用替換，並得到F（k）的= 4F（K/2） + 5 使用主定理我猜想它是O（logn）。這是否準確？

0熱度

1回答

主方法 - 分析

這是關於算法分析：說，有問題的運行時間是： T(n) = { 1, for n == 1 | T(n/3) + THETA(1), for n > 1} 現在，這是THETA(log base3 n) 但是，如果我用法師的方法，我評估爲THETA(log base2 n)，使用案例二我該如何從主方法得到正確答案？

1熱度

4回答

解決復發T（n）= T（n/2）+ lg n？

我遇到了一些關於如何解決遞歸關係的問題。 T（N）= T（N/2）+的log 2（N），T（1）= 1，其中n爲2 此電源是一個家庭作業的問題，所以不要只給我答案。我只是想知道如何開始這個問題。在課上我們去了the Master theorem。但我認爲這不是解決這種特殊關係的最好方法。我真的不知道如何下手這個問題......我應該只是被去 T(n) = T(n/2) + log_base2(

1熱度

2回答

尋找主定理的拉姆達

假設我有一個像 T(n)=2T(n/4)+log(n). a=2, b=4, f(n)=log(n) 的情況下，這應該是情況1，因爲n^(1/2)>log(n)。在情況1下還有拉姆達。f(n)=O(n^((1/2)-lambda)。它是否正確？我怎樣才能找到這個lambda？

3熱度

1回答

萬事達定理日誌N重組

如何理解主定理，算法可被遞歸地定義爲： a T(n/b) + O(n^d) 凡是子問題的數，n/b爲子問題的大小，和O（n^d）是子問題的重組時間。計算主定理的時間複雜度去如下： T(n) = { O(n^d) if d > log base b of a { { O(n^d log n) if d = log base b of a {

2熱度

2回答

碩士和f（n）的定理=日誌N

對於主定理T(n) = a*T(n/b) + f(n)我使用三種情況：如果a*f(n/b) = c*f(n)對於某一常數c > 1然後T(n) = (n^log(b) a) 如果a*f(n/b) = f(n)然後T(n) = (f(n) log(b) n) 如果a*f(n/b) = c*f(n)爲一些常數c < 1然後T(n) = (f(n)) 但是，當f(n) = log n或n*log n，

1熱度

2回答

寫函數的遞推關係

我知道遞歸關係的公式是T（n）= aT（n/b）+ f（n）。考慮到這個等式，我知道如何解決BigO。我的家庭作業問題要求我編寫一個遞歸函數來計算列表中的節點數，我做了，但後來要求我編寫一個遞歸關係。這裏是我的代碼： int count(ListNode *l) { if(!l) return 0; if(!l->next) return 1; return 1

5熱度

2回答

理解主定理

通用形式：T(n) = aT(n/b) + f(n) 所以，我必須比較N R個logb（a）用F（N）如果n^logba>f(n)是殼體1和T(n)=Θ(n^logb(a)) 如果n^logba < f(n) is case 2 and T(n)=Θ((n^logb(a))(logb(a))) 這是正確的嗎？或者我誤解了一些東西？那麼情況3呢？何時適用？

2熱度

1回答

查找閉端式的遞推方程由主定理

就可以解決這個 T(n) = 2T(n/2) + n lg n遞推方程主定理我從一個鏈接，他指出，因爲它沒有滿意，我們在這裏不能適用主定理來任何3ree情況。在另一方面，他已經採取了另一個例子 T(n) = 27T(n/3) + Θ(n^3 lg n)並找到閉解theta(n^3logn)爲了解決這個他用主定理的第二種情況If f(n) = Θ(nlogba (lg n)k) then T(n)