2011-gre-cs-practice-book.pdf/Q59 — различия между версиями
Материал из DISCOPAL
| Строка 22: | Строка 22: | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|43|59}} | {{cstest-source|2011-gre-cs-practice-book.pdf|43|59}} | ||
| − | На каждом уровне работы сумма затрат <m>cn<\m>, а глубина рекурсии порядка <m> \log n <\m>. Однако суммарная работа на всех уровнях по структуре делится так, что остаётся линейной: | + | На каждом уровне работы сумма затрат <m> cn <\m>, а глубина рекурсии порядка <m> \log n <\m>. Однако суммарная работа на всех уровнях по структуре делится так, что остаётся линейной: |
<m> T(n) \approx cn + c\frac{n}{2} + c\frac{n}{4} + \cdots \leq kn <\m> | <m> T(n) \approx cn + c\frac{n}{2} + c\frac{n}{4} + \cdots \leq kn <\m> | ||
Версия 18:57, 11 января 2025
Вопрос: Q59-08c765
Пусть T(n) определяется следующим образом:
,
где c — положительная константа, а — целое число.
Какая асимптотическая сложность функции T(n)?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 59 на 43 странице книги «2011-gre-cs-practice-book.pdf»
На каждом уровне работы сумма затрат