algorithm - 中位数算法中位数的时间复杂度

Question

你好，我这学期正在学习算法课程的介绍。但是我在计算中位数算法中位数的时间复杂度时遇到了一些问题（here）。我想知道如何获得T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn..

我认为我不能将 mater theorem 应用于上面的表达式，维基百科说我应该使用归纳，但我不知道如何..

Answer 1

它正在使用感应。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。证明完成！