master-theorem

1熱度

1回答

我嘗試從Mergesort計算複雜度。標準Mergesort具有遞推T（n）= T（n/2）+ T（n/2）+ n因此它很容易用主定理進行計算。（T）= T（2n/3）+ T（n/3）+ n 和T（n）= T（n-100）+ T如何計算Mergesort （100）？你能幫助我嗎？謝謝=）

0熱度

1回答

使用主定理求解重複T（n）= T（n/2）+ O（1）？

我試圖解決一個遞推關係，找出使用主定理及其復發概念的算法的複雜性，我怎麼能證明： T(n) = T(n/2)+O(1) 是 T(n) = O(log(n)) ? 任何解釋都會被認可！

0熱度

1回答

主定理與logn

這是problem。我真的很困惑的c等於0.5一部分。其實整體我很困惑如何logn可以變成。難道我不會讓c等於100這意味着100 < d這會導致使用不同的情況？我在這裏錯過了什麼？

0熱度

2回答

複製關係：T（n/16）+ n log n

主定理可以應用嗎？或者說對於T (n) = 2T (n/16) + n log n，主法則在這裏如何應用？我得到a = 2,b = 16，我不確定c和k。

0熱度

1回答

遞推樹猜測漸近上界。通過取代方法和主定理進行驗證

我的任務如下：通過使用遞歸樹查找遞歸漸近上界的圓環。驗證漸近上限爲： 1: Substitution method 2: Master Theorem T(n)= { Θ(1) if n = 1 { 3T(n/3) + Θ(n) if n > 1 我該如何處理這個問題？我有一些復發樹的知識，替代方法和主定理。請幫忙！

0熱度

1回答

隨機化快速排序選擇25％-75％的樞軸選擇

我知道，如果我們選擇樞軸的方式至少會在配給率25％的情況下進行隨機化快速排序， 75％，那麼運行時間是O(n log n)。現在我也知道我們可以用主定理證明這一點。但我的問題是，如果我們在每個步驟中將數組拆分爲25％-75％，那麼我將如何定義我的T(n)以及如何證明O(n log n)中的運行時分析？

1熱度

1回答

查找0（log^2（n））中的所有重硬幣

假設您獲得了n枚硬幣，其中一些硬幣很重，其他的硬幣很輕。所有重硬幣的重量都是一樣的，所有的輕硬幣也是如此，重硬幣的重量嚴格大於輕硬幣的重量。至少有一個硬幣是已知的輕。您將得到一個餘額，利用該餘額您可以將硬幣的子集與硬幣的另一個不相交的子集相比較。顯示如何使用 O（log2 n）稱量來確定重硬幣的數量。

0熱度

1回答

關於主定理證明的問題

我正在讀這本書CLRS（Introduction to Alglorithms，第3版），並發現在主定理的證明中似乎存在錯誤。在104頁，以延長證明所有的整數，它使用一個不等式，這似乎是不正確的。在書上它說：我們的第一個目標是確定深度k，使nk是一個常數。使用不等式[X] < = X + 1，我們得到 [X]在這裏是指x的天花板上，顯而易見的是，[x] < x+1，不[x] <= x+1。此外

-1熱度

1回答

如何找到這個算法的時間複雜度？

int multiply(int a[],int low,int high,int modulus) { if(low==high) return (a[low]); else { int mid = (low+high)/2; int x = multiply(a, low, mid, modulus) % modulus;

0熱度

1回答

解決複雜的復發關係

如何解決下面的復發關係？ T(n) = 2T(root(n)) + logn/loglogn if n > 4 T(n) = 1 if n <= 4 最好由主定理，否則通過任何方法。我知道主定理失敗了，但是這種類型的問題有沒有擴展？你能指導我解決上述複雜關係的任何東西嗎？