algorithm - 使用 Master 方法求解递归关系 -> 当 n 为偶数时 T(n) = 2T(n/2) + n^2 并且当 n 为奇数时 T(n) = 2T(n/2) + n^3

Question

T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd

我单独解决了这个问题，我得到的解决方案theta(n^2)好像 n 是偶数，theta(n^3)如果 n 是从 master 定理的案例 3 中得出的奇数。但我不应该单独解决这个问题。

如何一起解决这样的递归关系？

T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd

大师定理可以解决还是大师定理不适用？

请帮我解决这个问题。

标签： algorithmtime-complexityrecurrencemaster-theorem

Answer 1

假设n = 2^k某个整数k，所以n等于100...00。然后，您可以将主方法应用于重复的偶数部分。并获得theta(n^2).

现在假设最高有效位也1没有，例如100100..00。因此，您将在递归树中至少有一个级别，所有节点的总和为n^3 * constant，由此您获得theta(n^3).

因此，答案是theta(n^2)ifn是 2 的幂，theta(n^3)否则。但是如果我们第一次遇到奇数n并且它等于基本情况，那么它可能不是立方的。

---

在与 kelalaka 聊天之后，我想到如果 first1是k-th 从右边开始，n那么如果k > (2/3)(1/lg 2)lg n，我们不再关心(n/2^k)^3。它仍然是O(n^2)。