Древовидный метод с 8T (n / 2) + n ^ 2

Question

Я пытаюсь решить эту проблему, но думаю, что не понял, как это сделать правильно.Первое, что я делаю в этом типе упражнений, - это берут большее значение в строке (в данном случае n ^ 2) и делим его несколько раз, чтобы я мог выяснить, какая связь существует между значениями.После того, как найдено отношение, я пытаюсь математически найти его значение, а затем в качестве последнего шага я умножаю результат для корня.В этом случае результат должен быть n ^ 3.Как это возможно?

Answer 1

К сожалению, решения @ vahidreza кажутся мне ложными, потому что они противоречат основной теореме.В терминах основной теоремы a = 8, b = 2, c = 2.Итак, log_b(a) = 3, поэтому log_b(a) > c, и, следовательно, это случай рекурсии, в которой преобладают подзадачи, поэтому ответ должен быть T(n) = Ө(n^3), а не O(m^(2+1/3)), который имеет @vahidreza.

Вероятно, основная проблемав этом утверждении:

Также вы знаете, что дерево имеет log_8 m уровней.Потому что на каждом уровне вы делите число на 8.

Давайте попробуем решить это правильно:

• На нулевом уровне у вас есть n^2 (Я предпочитаю начинать считать с 0, так как это немного упрощает запись)

• на первом уровне у вас есть 8 узлов (n/2)^2 или всего 8*(n/2)^2

• на втором уровне у вас есть 8 * 8 узлов (n/(2^2))^2 или всего 8^2*(n/(2^2))^2

• на i -у вас есть 8^i узлов (n/(2^i))^2 или 8^i*(n/(2^i))^2 = n^2 * 8^i/2^(2*i) = n^2 * 2^i

На каждом уровне ваше значение n делится надва, поэтому на уровне i значение равно n/2^i, и поэтому у вас будет log_2(n) уровней.Так что вам нужно вычислить сумму для i от 0 до log_2(n) из n^2 * 2^i.Это геометрическая прогрессия с отношением 2, поэтому ее сумма равна

Σ (n^2 * 2^i) = n^2 * Σ(2^i) = n^2 * (2^(log_2(n)+1) - 1)/2

Поскольку мы говорим о Ө / O, мы можем игнорировать константы, поэтому нам нужно оценить

n^2 * 2^log_2(n)

Очевидно, 2^log_2(n) - это всего лишь n, поэтому ответ

T(n) = Ө(n^3)

в точности так, как предсказано в теореме Мастера.