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