你好，我正在学习算法类简介这个语义。但是，我在计算中位数算法(此处(的时间复杂度时遇到了一些问题。 我想知道如何获得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.证明完成！