2001-gre-vs-practice.pdf/Q42 — различия между версиями
Илья52 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Вопрос: Q42-e5724f == | == Вопрос: Q42-e5724f == | ||
| − | + | Определенный алгоритм выполняется за время <m> \mathcal{O}(N^{2.5}) </m> (см. [https://en.wikipedia.org/wiki/Big_O_notation O-нотацию]), где ''N'' размер входа алгоритма. | |
| − | + | ||
| − | Определенный алгоритм выполняется за время <m> \mathcal{O}(N^{2.5}) </m>, где | + | Какой из приведенных ниже вариантов НЕ верен для данного алгоритма. |
| − | + | ||
=== Ответы === | === Ответы === | ||
| Строка 21: | Строка 20: | ||
<m> \mathcal{O}(N^{2.5}) \Leftrightarrow \exists N_0 \exists C_1 : \forall N > N_0 \rightarrow T < C_1 N^{2.5} </m>, где <m> T </m> время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа <m> C_2 </m> убирает условие "начиная с некоторого <m> N_0 </m>", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение. | <m> \mathcal{O}(N^{2.5}) \Leftrightarrow \exists N_0 \exists C_1 : \forall N > N_0 \rightarrow T < C_1 N^{2.5} </m>, где <m> T </m> время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа <m> C_2 </m> убирает условие "начиная с некоторого <m> N_0 </m>", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение. | ||
| − | + | [[Участник:StasFomin|StasFomin]] 23:20, 27 декабря 2024 (UTC): Ха, так там же написано «НЕ верен». И неверен именно последний вариант. Остальные не противоречат описанию (можно расписывать, но это вам или еще кому-то, мне уже влом). Баллы я зачел, за попытку критичность (это правильно!), оставим как есть, надеюсь увидите правку. | |
| − | + | ||
| − | + | ||
| − | |||
| − | [[Участник:StasFomin|StasFomin]] | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 23:20, 27 декабря 2024 (UTC)}} |
| − | [[Категория: | + | [[Категория:Анализ временной сложности]] |
Текущая версия на 23:20, 27 декабря 2024
Вопрос: Q42-e5724f
Определенный алгоритм выполняется за время (см. O-нотацию), где N размер входа алгоритма.
Какой из приведенных ниже вариантов НЕ верен для данного алгоритма.
Ответы
- Существуют две константы и такие что, для любого время выполнения алгоритма будет меньше
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет больше чем секунд.
- Правильный ответ: Для любого существуют вход для которого время выполнения будет больше чем секунд.
Объяснение
Исходники — вопрос 42 на 35 странице книги «2001-gre-vs-practice.pdf»
Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.
, где время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа убирает условие "начиная с некоторого ", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение.
StasFomin 23:20, 27 декабря 2024 (UTC): Ха, так там же написано «НЕ верен». И неверен именно последний вариант. Остальные не противоречат описанию (можно расписывать, но это вам или еще кому-то, мне уже влом). Баллы я зачел, за попытку критичность (это правильно!), оставим как есть, надеюсь увидите правку.