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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 21: Строка 21:
 
Довольно спорный вопрос: если брать формальное определение, то 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-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду, но все-таки, тут ни в каком варианте не упомянуто, то что неравенство будет выполняться начиная с некоторого <m> N_0 </m>
  
 
https://en.wikipedia.org/wiki/Big_O_notation
 
https://en.wikipedia.org/wiki/Big_O_notation

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

Check-me-animated.gif Решено: илья52 18:21, 22 декабря 2024 (UTC)== Вопрос: 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