中位数的时间复杂度算法

本文介绍了中位数的时间复杂度算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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