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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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> C_1 N^{2.4} + C_2  </m> секунд.
−
# еще какой-то неправильный ответ
+
# Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> C_1 N^{2.6} + C_2  </m> секунд.
−
# еще какой-то неправильный ответ
+
# Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> C_1 N^{2.4} + C_2  </m> секунд.
−
# еще какой-то неправильный ответ
+
# Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> C_1 N^{2.6} + C_2  </m> секунд.
  
  
Строка 18: Строка 18:
 
{{cstest-source|2001-gre-vs-practice.pdf|35|42}}
 
{{cstest-source|2001-gre-vs-practice.pdf|35|42}}
  
−
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.
+
Правильный ответ: 5.  
  
−
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а [[2004-gre-cs-practice-book.pdf/Q16|неправильные варианты — неправильны]].
+
Довольно спорный вопрос, если брать формальное определение, то 2-5 варианты неправильные.  
−
Тут тоже могут быть полезны [[2004-gre-cs-practice-book.pdf/Q03|ссылки на википедию]],
+
 
−
решение вами [[2004-gre-cs-practice-book.pdf/Q12|рекуррентных уравнений в sympy]].
+
<m> \mathcal{O}(N^{2.5}) \Leftrightarrow \exists N_0 \exists C_1 : \forall N > N_0 T < C_1 N^{2.5} </m>
  
 
</i>
 
</i>

Версия 18:17, 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 варианты неправильные.

Источник — «https://discopal.ispras.ru/index.php?title=2001-gre-vs-practice.pdf/Q42&oldid=34696»