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

Версия 19:08, 23 декабря 2024 (просмотреть исходный код) StasFomin (обсуждение | вклад) ← Предыдущая правка		Версия 21:52, 25 декабря 2024 (просмотреть исходный код) Илья52 (обсуждение | вклад) Следующая правка →
Строка 7:		Строка 7:
	=== Ответы ===		=== Ответы ===
−	# Существуют две константы <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> N^{2.4} </m> секунд.	+	* Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.4} </m> секунд.
−	# Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.6} </m> секунд.	+	* Для любого <m> N </m> существуют вход для которого время выполнения будет меньше чем <m> N^{2.6} </m> секунд.
−	# Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.4} </m> секунд.	+	* Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.4} </m> секунд.
−	# Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.6} </m> секунд.	+	* Правильный ответ: Для любого <m> N </m> существуют вход для которого время выполнения будет больше чем <m> N^{2.6} </m> секунд.
	=== Объяснение ===		=== Объяснение ===
−	<i> {{cstest-source|2001-gre-vs-practice.pdf|35|42}}	+	{{cstest-source|2001-gre-vs-practice.pdf|35|42}}
−		+
−	Правильный ответ: 5.	+
	Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.		Довольно спорный вопрос: если брать формальное определение, то 2-5 варианты неправильные.
Строка 24:		Строка 22:
	https://en.wikipedia.org/wiki/Big_O_notation		https://en.wikipedia.org/wiki/Big_O_notation
−
−
−
−	</i>
	{{question-ok|}}		{{question-ok|}}

---

Версия 21:52, 25 декабря 2024

Вопрос: Q42-e5724f

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

Ответы

• Существуют две константы и такие что, для любого время выполнения алгоритма будет меньше
• Для любого существуют вход для которого время выполнения будет меньше чем секунд.
• Для любого существуют вход для которого время выполнения будет меньше чем секунд.
• Для любого существуют вход для которого время выполнения будет больше чем секунд.
• Правильный ответ: Для любого существуют вход для которого время выполнения будет больше чем секунд.

Объяснение

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

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

, где время выполнения алгоритма. Это общепринятое определение, я нигде не видел различий. Но все таки 5-ый вариант "самый неверный" из всех предложенных. Возможно в вопросе опечатка, если добавить во все варианты две константы, наподобие с первым вариантом, то больше будет похоже на правду. Потому что именно константа убирает условие "начиная с некоторого ", но во всех книгах в которых я помню определение (их как минимум 3) я не помню, чтобы так формулировали определение.

https://en.wikipedia.org/wiki/Big_O_notationStasFomin 19:04, 23 декабря 2024 (UTC): Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала все замечания по оформлению в канале, уже нет сил переделывать за всеми.