2011-gre-cs-practice-book.pdf/Q01 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q01-08c765 == | == Вопрос: Q01-08c765 == | ||
| − | < | + | Рассмотрим следующий псевдокод рекурсивной функции <tt>goAgain</tt> |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | <code-pascal> | |
| − | < | + | // assume N is a positive integer |
| − | ( | + | integer goAgain ( integer a, integer N ) |
| + | begin | ||
| + | if ( N == 1 ) then | ||
| + | return a | ||
| + | else | ||
| + | return a + goAgain ( a, N/2 ) | ||
| + | end | ||
| + | </code-pascal> | ||
| − | + | Каков порядок роста в зависимости от N количества рекурсивных вызовов функции goAgain? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | === Ответы === | |
| − | + | ||
| − | + | ||
| + | * Правильный ответ: <m>\theta(\log N)</m> | ||
| + | * <m>\theta(N)</m> | ||
| + | * <m>\theta(N \log N)</m> | ||
| + | * <m>\theta(N^2)</m> | ||
| + | * <m>\theta(N^3)</m> | ||
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|14|1}} | |
| − | {{cstest-source| | + | |
| + | Не уверен что тут действительно нужно какое-либо объяснение, но все же. | ||
| − | + | * <m>\theta(\log N)</m> — верно, поскольку функция каждый раз вызывает себя же с аргументом N вдвое меньшим, чем приняла на вход. В итоге к примеру для N = 16 функция будет вызвана со следующими аргументами: 16, 8, 4, 2, 1 — всего 5 раз, что соответствует ассимптотике <m>\theta(logN)</m>. | |
| + | * <m>\theta(N \log N)</m> — данная ассимптотика предполагает более чем линейный рост количества вызовов функции относительно N, что очевидно не так. | ||
| + | * <m>\theta(N)</m> — данная ассимптотика предполагает рост количества вызовов функции линейно зависимый от N. Однако это очевидно не так. | ||
| + | * <m>\theta(N^2)</m> — данная ассимптотика предполагает квадратичный рост количества вызовов функции в зависимости от N, что очевидно не верно. | ||
| + | * <m>\theta(N^3)</m> — данная ассимптотика предполагает кубический рост количества вызовов функции в зависимости от N, что очевидно не так. | ||
| − | {{question-ok|}} | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 19:16, 16 декабря 2024 (UTC)}} |
Текущая версия на 19:17, 16 декабря 2024
Вопрос: Q01-08c765
Рассмотрим следующий псевдокод рекурсивной функции goAgain
// assume N is a positive integer integer goAgain ( integer a, integer N ) begin if ( N == 1 ) then return a else return a + goAgain ( a, N/2 ) end
Каков порядок роста в зависимости от N количества рекурсивных вызовов функции goAgain?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 1 на 14 странице книги «2011-gre-cs-practice-book.pdf»
Не уверен что тут действительно нужно какое-либо объяснение, но все же.
- — верно, поскольку функция каждый раз вызывает себя же с аргументом N вдвое меньшим, чем приняла на вход. В итоге к примеру для N = 16 функция будет вызвана со следующими аргументами: 16, 8, 4, 2, 1 — всего 5 раз, что соответствует ассимптотике .
- — данная ассимптотика предполагает более чем линейный рост количества вызовов функции относительно N, что очевидно не так.
- — данная ассимптотика предполагает рост количества вызовов функции линейно зависимый от N. Однако это очевидно не так.
- — данная ассимптотика предполагает квадратичный рост количества вызовов функции в зависимости от N, что очевидно не верно.
- — данная ассимптотика предполагает кубический рост количества вызовов функции в зависимости от N, что очевидно не так.