Промежуточного этап рекуррентного соотношения Т (п) = 2T (п/2) + п/журнал (п)

Question

мне нужно помощь, чтобы понять один промежуточный шаг в решении следующего рекуррентное соотношения:

Через многократного замещение я получил весь путь до:

Это где я застрял. Все говорят, что вторая часть равна

Я пытался много манипуляций, и я не могу понять, как получить здесь.

Итак - два вопроса:

1. Почему границы на сумму, идущей от 1 до журнала (п)?
2. Как вы достигаете этого суммирования из последовательности, которая у меня есть? Я знаю, что последовательность также записывается в виде

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

Answer 1

Так что прежде всего такие рецидивы решаются с помощью Master's theorem. Вы спросили, почему так объясняется.

Первый вопрос: почему вы суммируете от 1 до log n. Его легко: вы начинаете с номера n и каждый раз, когда вы его уменьшаете на 2 раз. Итак, насколько быстро он приблизится к n? После log n раз (log означает log2 здесь). Если это неясно, замените n на 2^k.

Теперь вторая часть. Ваш я-й элемент (Если эти элементарные операции журнала не ясны для вас, вы должны обновить свои знания о логарифмов):

Теперь должно быть понятно, почему ваше решение эквивалентно к их ,

Answer 2

Вы разворачивались ваш рецидив к раз, чтобы добраться до

Это означает, что п = 2 ^к так:

1. входа по обе стороны этого уравнение log (n) = log (2 ^k) = k, который отвечает, почему суммирование связано идет в журнал (п)
2. заменой для п в каждом члене суммирования и вы получите:

Наконец:

Две стороны просто записывают гармонические ряды в обратном порядке друг друга.