Выведено как T (n) = O (n). Но я не могу доказать это из метода замещения. Пожалуйста, подтвердите свой ответ.Я хочу нарисовать дерево рекурсии для T (n) = 3T (n/2) + n и получить предположение к верхней границе
Я не собираюсь доказывать это вам, потому что я думаю, что это, вероятно, проблема домашних заданий, и у меня есть этические заботы о выполнении вашей домашней работы для вас , Тем не менее, я был бы рад дать вам понять, почему у вас возникают проблемы с доказательством того, что T (n) = 3T (n/2) + n.
Давайте подумаем о дереве рекурсии. На верхнем уровне у нас есть один узел размера n, который работает n. Ниже он имеет три узла размером n/2, каждый из которых работает n/2. Суммируя эту строку, мы видим, что выполненная работа - 3n/2. Каждый из этих трех узлов генерирует три новых узла размером n/4. Это означает, что на следующем уровне есть девять узлов, каждый из которых выполняет n/4, поэтому общая работа над этим слоем равна 9n/4.
Если вы следуете рисунку здесь, вы заметите, что работа, выполненная в k-м слое, равна (3/2) k n. Это возрастает с ростом k, поэтому на самом деле работа не будет O (n).
Играйте с этим наблюдением и с помощью итерационного метода. Сколько слоев будет? Исходя из этого, какова будет время выполнения?