2001-gre-vs-practice.pdf/Q42

Решено: илья52 18:21, 22 декабря 2024 (UTC)== Вопрос: Q42-e5724f ==

Задача зарезервирована: илья52 11:07, 21 декабря 2024 (UTC)

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

Ответы

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

Объяснение

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

Правильный ответ: 5.

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

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