Q: Решение следующего повторения: T (n) = 8T (n / 8) + n log n

Question

Я пытаюсь решить следующую проблему:

T(n) = 8T(n/8) + n* log n. 

В настоящее время я сделал следующее, но не уверен, что нахожусь на правильном пути:

1. T(n)= 8 T(n/8) + n log n;
2. T(n)= 8^2 T(n/8^2) + n log (n/8) + n log n
3. T(n)= 8^3 T(n/8^3) + n log (n/8^2) + n log (n/8) + n log n

Итак, общая формула пришла мне в голову:

T(n)= 8^k T(n/8^k) + n log(n* n/8 * n/8^2 * ... * n/8^k).

И я не уверен, как продолжить это. Я пытался переписать log как n^k / 8^(k*(k+1)/2), но я до сих пор не вижу решения.

Answer 1

Вы почти у цели.Установите k = log_8(n), тогда вы можете решить для T(n)