У меня повторяющийся вопрос, который сводится к суммированию логов, но я не могу его решить.Любая помощь приветствуется.
T (n) = 2T (n / 2) + nlog (n)
T (1) = 1
Я нарисовал дерево повторений и знаю, что оно имеетглубина журнала (n).
Я понял, что O (n) = nlog (n) + nlog (n / 2) + nlog (n / 4) + ... + n
это имеет журнал (n) члены
Если взять n, то возникает следующая проблема суммирования:
n * суммирование i = 0 для log (n) журнала (n / 2 ^ i)
Я не уверенкак решить это суммирование
РЕДАКТИРОВАТЬ: все базы для журналов 2