中位数的时间复杂度算法 [英] Time complexity of median of medians algorithm

问题描述

您好，我正在学习本课程的算法类简介。但是，我在计算中位数算法的时间复杂度时遇到了一些问题（此处）。
我想知道如何从T（n）< = T（0.2n）+ T（0.7n）+ cn。<< c $ c> T（n）< = 10cn。

Hello I am taking Introduction to algorithm class this semeseter. However I have some problem in calculating time complexity of median of medians algorithm (here). I'm wondering how to get T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn..

我想我不能对上面的表达式应用母定理，而维基百科说我应该使用归纳法，但是我不知道怎么做。 >

I think I cannot apply mater theorem to the expression above and wikipedia says I should use induction but I don't know How..

推荐答案

它使用归纳法。
假设小于或等于 n ，我们有 T（n）< = 10 * c * n （我们知道归纳的基数对于等于或小于 T（10）是正确的，因为它们是常数，我们可以对使用足够大的值c ）。现在，我们要针对 T（n + 1）证明这一点。我们知道 T（n + 1）< = T（0.2（n + 1））+ T（0.7（n + 1））+ c（n + 1） 。从归纳假设为 0.2（n + 1）和 0.7（n + 1）小于 n （对于 n> 10 ）， T（0.2（n + 1））< ; = 10 * c * 0.2（n + 1）和 T（0.7（n + 1））< = 10 * c * 0.7（n + 1）。因此， T（n + 1）< = 2 * c（n + 1）+ 7 * c（n + 1）+ n * c = 10 * c * n 。证明完成了！

It is using induction. Assume for less than or equal n we have T(n) <= 10*c*n (we know the base of induction is true for equal or less than T(10) as they are constant and we can use large enough value for c). Now we want to prove this for T(n + 1). We know T(n + 1) <= T(0.2(n + 1)) + T(0.7( n + 1)) + c(n+1). From the assumption of the induction as 0.2(n + 1) and 0.7(n+1) is less than n (for n > 10), T(0.2(n + 1)) <= 10*c*0.2(n + 1) and T(0.7(n + 1)) <= 10*c*0.7(n + 1). Therefore, T(n+1) <= 2*c(n+1) + 7*c(n+1) + n*c = 10*c*n. The proof is completed!

这篇关于中位数的时间复杂度算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！