2001-gre-vs-practice.pdf/Q42 — различия между версиями
StasFomin (обсуждение | вклад) |
Илья52 (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Вопрос: Q42-e5724f == | == Вопрос: Q42-e5724f == | ||
| − | {{reserve-task|[[Участник:Илья52|илья52]] 11:07, 21 декабря 2024 (UTC)}} | + | {{checkme|[[Участник:Илья52|илья52]] 21:58, 25 декабря 2024 (UTC)}}{{reserve-task|[[Участник:Илья52|илья52]] 11:07, 21 декабря 2024 (UTC)}} |
<blockquote> | <blockquote> | ||
Определенный алгоритм выполняется за время <m> \mathcal{O}(N^{2.5}) </m>, где <m> N </m> размер входа алгоритма. Какой из приведенных ниже вариантов НЕ верен для данного алгоритма. | Определенный алгоритм выполняется за время <m> \mathcal{O}(N^{2.5}) </m>, где <m> N </m> размер входа алгоритма. Какой из приведенных ниже вариантов НЕ верен для данного алгоритма. | ||
| Строка 7: | Строка 7: | ||
=== Ответы === | === Ответы === | ||
| − | + | * Существуют две константы <m>C_1</m> и <m>C_2</m> такие что, для любого <m> N </m> время выполнения алгоритма будет меньше <m> C_1 N^{2.5} + C_2 </m> | |
| − | + | * Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.4} </m> секунд. | |
| − | + | * Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.6} </m> секунд. | |
| − | + | * Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.4} </m> секунд. | |
| − | + | * Правильный ответ: Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.6} </m> секунд. | |
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2001-gre-vs-practice.pdf|35|42}} | |
| − | + | ||
| − | + | ||
Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные. | Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные. | ||
| Строка 24: | Строка 22: | ||
https://en.wikipedia.org/wiki/Big_O_notation | https://en.wikipedia.org/wiki/Big_O_notation | ||
| − | |||
| − | |||
| − | |||
| − | |||
{{question-ok|}} | {{question-ok|}} | ||
Текущая версия на 21:58, 25 декабря 2024
Вопрос: Q42-e5724f
Решено: илья52 21:58, 25 декабря 2024 (UTC)
Задача зарезервирована: илья52 11:07, 21 декабря 2024 (UTC)
Определенный алгоритм выполняется за время , где размер входа алгоритма. Какой из приведенных ниже вариантов НЕ верен для данного алгоритма.
Ответы
- Существуют две константы и такие что, для любого время выполнения алгоритма будет меньше
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет больше чем секунд.
- Правильный ответ: Для любого существуют вход для которого время выполнения будет больше чем секунд.
Объяснение
Исходники — вопрос 42 на 35 странице книги «2001-gre-vs-practice.pdf»
Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.
, где время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа убирает условие "начиная с некоторого ", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение.
https://en.wikipedia.org/wiki/Big_O_notation