2019-gate-computer-science-and-it-practice.pdf/Q02-alg3 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q02-alg3-31d68c == <blockquote> Вопрос из «Algorithms Test 3» где-то со страницы 233. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q02-alg3-31d68c == | == Вопрос: Q02-alg3-31d68c == | ||
| − | < | + | Пусть ''M'' является целым числом, которое больше единицы. Какая асимптотика роста функции <m>\sum_{i = 1}^n M^i</m> является верной? |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>\Theta(n^M)</m> |
| − | ( | + | * <m>\Theta(M^{2n+1})</m> |
| − | + | * <m>\Theta(M^{n\log n})</m> | |
| − | * Правильный ответ: | + | * Правильный ответ: <m>\Theta(M^n)</m> |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | < | + | Расписывая формулу суммы геометрической прогрессии получим, что сумма степеней ''M'' равна: <m>\Theta(M^n)</m>. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|233|2}} |
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 09:56, 25 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Ряды]] |
Текущая версия на 09:56, 25 декабря 2024
Вопрос: Q02-alg3-31d68c
Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?
Ответы
- Правильный ответ:
Объяснение
Расписывая формулу суммы геометрической прогрессии получим, что сумма степеней M равна: .
Исходники — вопрос 2 на 233 странице книги «2019-gate-computer-science-and-it-practice.pdf»