2011-gre-cs-practice-book.pdf/Q59

Ссылки сюда (1) →

Вопрос: Q59-08c765

Пусть T(n) определяется следующим образом:

• ,
• где c — положительная константа, а — целое число.

Какая асимптотическая сложность функции T(n)?

Ответы

• Правильный ответ:

Объяснение

Исходники — вопрос 59 на 43 странице книги «2011-gre-cs-practice-book.pdf»

На каждом уровне работы сумма затрат , а глубина рекурсии порядка . Однако суммарная работа на всех уровнях по структуре делится так, что остаётся линейной:

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.