2001-gre-vs-practice.pdf/Q58 — различия между версиями
Материал из DISCOPAL
(→Вопрос: Q58-e5724f) |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
== Вопрос: Q58-e5724f == | == Вопрос: Q58-e5724f == | ||
| − | + | Какую из следующих функций можно считать наилучшей верхней границей для значения <m>\( f(N) \)</m>, | |
| − | Какую из следующих функций можно считать наилучшей верхней границей для значения <m>\( f(N) \)</m>, где <m>\( f \)</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> | ||
| Строка 18: | Строка 14: | ||
=== Объяснение === | === Объяснение === | ||
| − | {{cstest-source|2001-gre-vs-practice.pdf|41 | + | {{cstest-source|2001-gre-vs-practice.pdf|41|58}} |
У нас есть два варианта рекурсии: | У нас есть два варианта рекурсии: | ||
| Строка 36: | Строка 32: | ||
Это дает нам оценку <m>\( O(\log^2 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»
У нас есть два варианта рекурсии: и
Рассмотрим, что происходит на каждом шаге рекурсии. Каждый раз мы делим пополам и добавляем . Это аналогично тому, как в процессе рекурсии мы получаем сумму логарифмов на каждом шаге: Каждый шаг добавляет , и количество шагов примерно равно , так как делится пополам на каждом шаге.
Это дает нам оценку .