medians of medians算法的时间复杂度
Time complexity of median of medians algorithm
你好，我这学期要学习算法导论class。但是我在计算中位数算法（here）的时间复杂度时遇到了一些问题。
我想知道如何获得 T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn..
我想我不能将数学定理应用于上面的表达式，维基百科说我应该使用归纳法，但我不知道如何......
正在使用归纳法。
假设小于或等于 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。证明完成！
你好，我这学期要学习算法导论class。但是我在计算中位数算法（here）的时间复杂度时遇到了一些问题。
我想知道如何获得 T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn..
我想我不能将数学定理应用于上面的表达式，维基百科说我应该使用归纳法，但我不知道如何......
正在使用归纳法。
假设小于或等于 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。证明完成！