2001-gre-vs-practice.pdf/Q58 — различия между версиями
Материал из DISCOPAL
(→Вопрос: Q58-e5724f) |
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> | ||
| Строка 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»
У нас есть два варианта рекурсии: и
Рассмотрим, что происходит на каждом шаге рекурсии. Каждый раз мы делим пополам и добавляем . Это аналогично тому, как в процессе рекурсии мы получаем сумму логарифмов на каждом шаге: Каждый шаг добавляет , и количество шагов примерно равно , так как делится пополам на каждом шаге.
Это дает нам оценку .