2001-gre-vs-practice.pdf/Q42 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 20: Строка 20:
 
Правильный ответ: 5.  
 
Правильный ответ: 5.  
  
Довольно спорный вопрос, если брать формальное определение, то 2-5 варианты неправильные.  
+
Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.  
  
 
<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> \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-ый вариант "самый неверный" из всех предложенных.

Версия 18:21, 22 декабря 2024

Вопрос: Q42-e5724f

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

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

Ответы

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


Объяснение

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

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

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

, где время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных.

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