使用非主定理解决递归方程问题
所以，在之前的一次考试中，我被要求解决以下递归方程而不使用主定理： T(n)= 9T(n/3) + n^2 很遗憾，我在考试中无法解决它，所以我使用了主定理来解决它，只是为了知道答案（但当然，我没有得到这个问题的学分），现在我想知道如何在没有主定理的情况下解决它，因为在期末考试中，会有类...
理解主定理
通用形式: T(n) = aT(n/b) + f(n) 因此，我必须比较 n^logb(a) 和 f(n) 如果 n^logba > f(n)，则为情况1，且T(n)=Θ(n^logb(a)) 如果 n^logba < f(n)，则为情况2，且T(n)=Θ((n^logb(a...
主定理：当f(n)包含log的负指数时会出现问题。
我正在使用主定理计算以下函数的平均情况复杂度： T(n) = 2T (n/2)+ n/ log n 根据http://people.csail.mit.edu/thies/6.046-web/master.pdf中的问题7， 上面写着 不适用（f(n)和n log b a 之间存在非...
算法时间复杂度分析：关系式 T(n) = T(n-1) + T(n/2) + n 的时间复杂度是什么？
对于这个关系式： T(n) = T(n-1) + T(n/2) + n 我可以先解决项 (T(n-1) + n)，得到 O(n^2)，然后再解决项 T(n/2) + O(n^2) 吗？ 根据主定理，这同样会得到 O(n^2) 吗？还是说这种方法是错误的？
主定理中 f(n)=log n 的情况
对于主定理 T(n) = a*T(n/b) + f(n)，我使用3种情况： 如果存在一个常数 c > 1，使得 a*f(n/b) = c*f(n)，那么 T(n) = (n^log(b) a) 如果 a*f(n/b) = f(n)，则 T(n) = (f(n) log(b) n) 如...
主定理实际上可以在什么情况下应用？
我对此感到非常沮丧。 在CLRS第三版的第95页（第4.5章）中提到，像 T(n) = 2T(n/2) + n lg n 这样的递归无法用主定理解决，因为差异 f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n 不是多项式。 但是我发现像这个网页底部提到...