2011-gre-cs-practice-book.pdf/Q59 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 27: Строка 27:
  
 
{{question-ok|}}
 
{{question-ok|}}
−
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:58, 8 января 2025 (UTC)}}
+
{{checkme|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:56, 11 января 2025 (UTC)}}

Версия 20:56, 11 января 2025

Вопрос: Q59-08c765

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

,

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

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

Ответы

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

Объяснение

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

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

Check-me-animated.gif Решено: Nikitashapovalov 20:56, 11 января 2025 (UTC)

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q59&oldid=35636»