2001-gre-vs-practice.pdf/Q58 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q58-e5724f == <blockquote> Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D…») |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q58-e5724f == | == Вопрос: Q58-e5724f == | ||
| − | + | Какую из следующих функций можно считать наилучшей верхней границей для значения <m>\( f(N) \)</m>, | |
| − | < | + | * где <m>\( f \)</m> — это решение рекуррентного соотношения |
| − | + | <m>\[ f(2N + 1) = f(2N) = f(N) + \log N \text{ для } N \geq 1, \] </m> | |
| − | + | с начальным условием <m>\( f(1) = 0 \)</m>? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>\( O(\log N) \) </m> |
| − | ( | + | * <m>\( O(N \log N) \) </m> |
| − | + | * <m>\( O(\log N) + O(1) \) </m> | |
| − | * | + | * Правильный ответ: <m>\( O((\log N)^2) \) </m> |
| − | * | + | * <m>\( O(N) \) </m> |
| − | * | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | |||
| − | |||
| − | + | {{cstest-source|2001-gre-vs-practice.pdf|41|58}} | |
| − | + | У нас есть два варианта рекурсии: | |
| − | + | <m>\[ | |
| − | + | f(2N) = f(N) + \log N | |
| + | \]</m> | ||
| + | и | ||
| + | <m>\[ | ||
| + | f(2N + 1) = f(N) + \log N. | ||
| + | \]</m> | ||
| − | </ | + | Рассмотрим, что происходит на каждом шаге рекурсии. Каждый раз мы делим <m>\( N \)</m> пополам и добавляем <m>\( \log N \)</m>. Это аналогично тому, как в процессе рекурсии мы получаем сумму логарифмов на каждом шаге: |
| + | <m>\[f(N) \approx \sum_{k=0}^{\log N} \log (2^k). | ||
| + | \]</m> | ||
| + | Каждый шаг добавляет <m>\( \log N \)</m>, и количество шагов примерно равно <m>\( \log N \)</m>, так как <m>\( N \)</m> делится пополам на каждом шаге. | ||
| + | |||
| + | Это дает нам оценку <m>\( O(\log^2 N) \)</m>. | ||
| − | {{question-ok|}} | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 08:01, 6 января 2025 (UTC)}} |
| − | [[ | + | [[Категория:Рекуррентные соотношения]] |
Текущая версия на 08:01, 6 января 2025
Вопрос: Q58-e5724f
Какую из следующих функций можно считать наилучшей верхней границей для значения ,
- где — это решение рекуррентного соотношения
с начальным условием ?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 58 на 41 странице книги «2001-gre-vs-practice.pdf»
У нас есть два варианта рекурсии: и
Рассмотрим, что происходит на каждом шаге рекурсии. Каждый раз мы делим пополам и добавляем . Это аналогично тому, как в процессе рекурсии мы получаем сумму логарифмов на каждом шаге: Каждый шаг добавляет , и количество шагов примерно равно , так как делится пополам на каждом шаге.
Это дает нам оценку .