2001-gre-vs-practice.pdf/Q42 — различия между версиями
Материал из DISCOPAL
Илья52 (обсуждение | вклад) |
Илья52 (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
# Существуют две константы <m>C_1</m> и <m>C_2</m> такие что, для любого <m> N </m> время выполнения алгоритма будет меньше <m> C_1 N^{2.5} + C_2 </m> | # Существуют две константы <m>C_1</m> и <m>C_2</m> такие что, для любого <m> N </m> время выполнения алгоритма будет меньше <m> C_1 N^{2.5} + C_2 </m> | ||
| − | # Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> | + | # Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.4} </m> секунд. |
| − | # Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> | + | # Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.6} </m> секунд. |
| − | # Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> | + | # Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.4} </m> секунд. |
| − | # Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> | + | # Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.6} </m> секунд. |
Версия 18:20, 22 декабря 2024
Вопрос: Q42-e5724f
Задача зарезервирована: илья52 11:07, 21 декабря 2024 (UTC)
Определенный алгоритм выполняется за время , где размер входа алгоритма. Какой из приведенных ниже вариантов НЕ верен для данного алгоритма.
Ответы
- Существуют две константы и такие что, для любого время выполнения алгоритма будет меньше
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет меньше чем секунд.
- Для любого существуют вход для которого время выполнения будет больше чем секунд.
- Для любого существуют вход для которого время выполнения будет больше чем секунд.
Объяснение
Сначала заполните номер страницы с этим вопросом Исходники — вопрос 42 на 35 странице книги «2001-gre-vs-practice.pdf»
Правильный ответ: 5.
Довольно спорный вопрос, если брать формальное определение, то 2-5 варианты неправильные.
, где время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных.
https://en.wikipedia.org/wiki/Big_O_notation