2011-gre-cs-practice-book.pdf/Q59 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| (не показано 6 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Вопрос: Q59-08c765 == | == Вопрос: Q59-08c765 == | ||
| − | < | + | Пусть ''T(n)'' определяется следующим образом: |
| − | + | * <m> T(0) = T(1) = 4 </m> | |
| − | + | * <m> T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lfloor \frac{n}{4} \right\rfloor\right) + cn</m>, | |
| − | + | * где ''c'' — положительная константа, а <m> n \geq 2 </m> — целое число. | |
| − | + | Какая асимптотическая сложность функции ''T(n)''? | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m> \Theta(\log n) </m> |
| − | ( | + | * Правильный ответ: <m> \Theta(n) </m> |
| + | * <m> \Theta(n \log n) </m> | ||
| + | * <m> \Theta(n^2) </m> | ||
| + | * <m> \Theta(n^{\log_3 4}) </m> | ||
| − | + | === Объяснение === | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|43|59}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | {{cstest-source|2011-gre-cs-practice-book.pdf| | + | |
| − | + | На каждом уровне работы сумма затрат <m> cn </m>, а глубина рекурсии порядка <m> \log n </m>. Однако суммарная работа на всех уровнях по структуре делится так, что остаётся линейной: | |
| − | + | <m> T(n) \approx cn + c\frac{n}{2} + c\frac{n}{4} + \cdots \leq kn </m> | |
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 21:41, 11 января 2025 (UTC)}} | |
| − | + | [[Категория:Рекуррентные соотношения]] | |
| − | + | ||
Текущая версия на 21:41, 11 января 2025
Вопрос: Q59-08c765
Пусть T(n) определяется следующим образом:
- ,
- где c — положительная константа, а — целое число.
Какая асимптотическая сложность функции T(n)?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 59 на 43 странице книги «2011-gre-cs-practice-book.pdf»
На каждом уровне работы сумма затрат , а глубина рекурсии порядка . Однако суммарная работа на всех уровнях по структуре делится так, что остаётся линейной: