2001-gre-vs-practice.pdf/Q42

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

Вопрос: Q42-e5724f

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

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

Ответы

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

Объяснение

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

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

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

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

https://en.wikipedia.org/wiki/Big_O_notation

StasFomin 19:04, 23 декабря 2024 (UTC): Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала все замечания по оформлению в канале, уже нет сил переделывать за всеми.

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

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

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