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