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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: « == Вопрос: Q42-e5724f == <blockquote> Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D…»)
 
 
(не показано 14 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
+
{{checkme|[[Участник:Илья52|илья52]] 18:21, 22 декабря 2024 (UTC)}}== Вопрос: Q42-e5724f ==
== Вопрос: Q42-e5724f ==
+
{{reserve-task|[[Участник:Илья52|илья52]] 11:07, 21 декабря 2024 (UTC)}}
 
+
 
<blockquote>
 
<blockquote>
Тут вставьте перевод вопроса.
+
Определенный алгоритм выполняется за время <m> \mathcal{O}(N^{2.5}) </m>, где <m> N </m> размер входа алгоритма. Какой из приведенных ниже вариантов НЕ верен для данного алгоритма.
Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 возможности разметки],
+
</blockquote>
включая формулы и т.п, если будут графы — посмотрите как задать их текстом https://wiki.4intra.net/Graphviz (реально оценю, полезный навык).
+
Если код — теги «code-pascal», «code-c» или «code-python» (не «source lang»).
+
  
В IT вообще не принято писать романы, всегда старайтесь писать структурированные (списками-абзацами тексты). Списки в MediaWiki — это просто «*». Не забывайте о них.
+
=== Ответы ===
Преформатированный моноширинный текст — просто отступ.
+
  
Старайтесь нетривиальные понятия, особенно незнакомые вам, найти ссылку на википедию и вставить (нейросети лажают!).
+
# Существуют две константы <m>C_1</m> и <m>C_2</m> такие что, для любого <m> N </m> время выполнения алгоритма будет меньше <m> C_1 N^{2.5} + C_2  </m>
Это важно, чтобы найти корректный перевод (то, что в википедии, или на худой конец — точно массово гуглится).
+
# Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.4} </m> секунд.
 +
# Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.6} </m> секунд.
 +
# Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.4} </m> секунд.
 +
# Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.6} </m> секунд.
  
Потом конечно сотрите эти инструкции, которые тут курсивом или в блоке цитирования.
 
</blockquote>
 
  
=== Ответы ===
+
=== Объяснение ===
<i>Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так
+
<i> {{cstest-source|2001-gre-vs-practice.pdf|35|42}}
(префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)</i>
+
  
* Правильный ответ: тут реально правильный ответ
+
Правильный ответ: 5.
* неправильный ответ
+
* еще какой-то неправильный ответ
+
* еще какой-то неправильный ответ
+
* еще какой-то неправильный ответ
+
  
<i>Если ответы длинные, многострочные, или там графы, используйте
+
Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.  
[https://wiki.4intra.net/MediawikiQuizzer/ru#.D0.9E.D1.82.D0.B2.D0.B5.D1.82.D1.8B способ задания ответов разделами],  
+
Но такое очень редко встречается, например [[2011-gre-cs-practice-book.pdf/Q05]]. </i>
+
  
 +
<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> C_2 </m> убирает условие "начиная с некоторого <m> N_0 </m>", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение.
  
=== Объяснение ===
+
https://en.wikipedia.org/wiki/Big_O_notation
<i>Сначала заполните номер страницы с этим вопросом
+
{{cstest-source|2001-gre-vs-practice.pdf|тут-номер-страницы-с-вопросом-42|42}}
+
  
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.
 
  
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а [[2004-gre-cs-practice-book.pdf/Q16|неправильные варианты — неправильны]].
 
Тут тоже могут быть полезны [[2004-gre-cs-practice-book.pdf/Q03|ссылки на википедию]],
 
решение вами [[2004-gre-cs-practice-book.pdf/Q12|рекуррентных уравнений в sympy]].
 
  
 
</i>
 
</i>
Строка 46: Строка 31:
 
{{question-ok|}}
 
{{question-ok|}}
  
[[Category:Надо не забыть выбрать тему]]
+
[[Категория:Надо не забыть выбрать тему]]

Текущая версия на 18:27, 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-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа убирает условие "начиная с некоторого ", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение.

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