В чем сложность алгоритма: T (n) = 3 * T (n ÷ b) + n² + 1? - PullRequest
1 голос
/ 18 марта 2019

В чем сложность алгоритма: T (n) = 3 * T (n ÷ b) + n² + 1? Задайте вопрос

один

Можете ли вы помочь мне узнать, в чем состоит сложность: T (n) = 3 * T (n ÷ b) + n² + 1. Когда n> 1?.

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

Спасибо!

1 Ответ

2 голосов
/ 18 марта 2019

Если b равно 1, критический коэффициент мастера не определен и условие регулярности не выполняется.T (n) в этом случае вообще не может быть четко определено и не имеет разумных решений.

Если b равно 2, критический коэффициент основной теоремы равен log_2 (3) и n ^ log_2(3) = O (n ^ 2)… также, поскольку T (n) удовлетворяет регулярности в этом случае, теорема Мастера говорит нам, что здесь сложность O (n ^ 2).

Действительно, для любогоb больше 2, вышеупомянутый анализ также применим: log_b (3) всегда меньше 2 для целых чисел b больше 1. Для любого такого выбора регулярность будет выполняться, поэтому мы всегда находимся в случае 3 основной теоремы ииметь это T (n) = O (n ^ 2).

...