2001-gre-vs-practice.pdf/Q42

Ссылки сюда (1) →

Вопрос: Q42-e5724f

Определенный алгоритм выполняется за время (см. O-нотацию), где N размер входа алгоритма.

Какой из приведенных ниже вариантов НЕ верен для данного алгоритма.

Ответы

• Существуют две константы и такие что, для любого время выполнения алгоритма будет меньше
• Для любого существуют вход для которого время выполнения будет меньше чем секунд.
• Для любого существуют вход для которого время выполнения будет меньше чем секунд.
• Для любого существуют вход для которого время выполнения будет больше чем секунд.
• Правильный ответ: Для любого существуют вход для которого время выполнения будет больше чем секунд.

Объяснение

Исходники — вопрос 42 на 35 странице книги «2001-gre-vs-practice.pdf»

Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.

, где время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа убирает условие "начиная с некоторого ", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение.

StasFomin 23:20, 27 декабря 2024 (UTC): Ха, так там же написано «НЕ верен». И неверен именно последний вариант. Остальные не противоречат описанию (можно расписывать, но это вам или еще кому-то, мне уже влом). Баллы я зачел, за попытку критичность (это правильно!), оставим как есть, надеюсь увидите правку.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.