2001-gre-vs-practice.pdf/Q42 — различия между версиями
Илья52 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | == Вопрос: Q42-e5724f == | |
{{reserve-task|[[Участник:Илья52|илья52]] 11:07, 21 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Илья52|илья52]] 11:07, 21 декабря 2024 (UTC)}} | ||
<blockquote> | <blockquote> | ||
| Строка 30: | Строка 30: | ||
{{question-ok|}} | {{question-ok|}} | ||
| + | |||
| + | {{Badsol}} | ||
| + | |||
| + | [[Участник:StasFomin|StasFomin]] 19:04, 23 декабря 2024 (UTC): Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала [https://t.me/c/2489499765/78/191 все замечания по оформлению в канале], уже нет сил переделывать за всеми. | ||
[[Категория:Надо не забыть выбрать тему]] | [[Категория:Надо не забыть выбрать тему]] | ||
Версия 19:08, 23 декабря 2024
Вопрос: Q42-e5724f
Задача зарезервирована: илья52 11:07, 21 декабря 2024 (UTC)
Определенный алгоритм выполняется за время , где размер входа алгоритма. Какой из приведенных ниже вариантов НЕ верен для данного алгоритма.
Ответы
- Существуют две константы и такие что, для любого время выполнения алгоритма будет меньше
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет больше чем секунд.
- Для любого существуют вход для которого время выполнения будет больше чем секунд.
Объяснение
Исходники — вопрос 42 на 35 странице книги «2001-gre-vs-practice.pdf»
Правильный ответ: 5.
Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.
, где время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа убирает условие "начиная с некоторого ", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение.
https://en.wikipedia.org/wiki/Big_O_notation
