Повторение: T (n / 4) + T (n / 2) + n ^ 2 с методами дерева

Question

Я пытаюсь решить это упражнение методом дерева, но у меня есть сомнения по поводу двух частей: 1) В столбце T (?) правильно ли это с помощью (n ^ 2/2)^ i) вместо (n / 2 ^ i)?Я спрашиваю, потому что это та часть, которая вызывает у меня ошибку;2) Правильно ли последнее умножение (оно между числом узлов и временем)?После нахождения значения i я должен создать серию, которая начинается с 0 до результата умножения, верно?И как переменная серии я должен использовать 2 ^ я (количество узлов)?

Answer 1

Столбец для количества узлов вводит в заблуждение.

Каждый узел имеет стоимость (m/k)^2, где k равен знаменателю узла.В структуре, которую вы используете, узлы на каждом уровне будут иметь различные знаменатели.Например, ваш уровень 2 должен содержать узлы [(m / 16), (m / 8)], [(m / 8), (m / 4)].

Стоимость уровня - это сумма стоимости каждого узла на этом уровне.Поскольку каждый узел имеет свою стоимость, вы не можете умножить количество узлов на значение, чтобы найти стоимость уровня, вы должны сложить их по отдельности.

Общая стоимость представляет собой сумму стоимостикаждый уровень.Результатом этого вычисления может быть логарифм, а может и нет.Это зависит от стоимости каждого уровня и количества уровней.

Подсказка: треугольник Паскаля