Временная сложность алгоритма медианы медиан

Question

Здравствуйте, я беру Введение в алгоритм класса этого семесетера. Однако у меня есть некоторая проблема в вычислении временной сложности алгоритма медианы медиан ( здесь). Мне интересно как получить T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn..

Я думаю, что я не могу применить теорему о математике к вышеприведенному выражению, и википедия говорит, что я должен использовать индукцию, но я не знаю, как...

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, Доказательство завершено!