2011-gre-cs-practice-book.pdf/Q32 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Ответы)
 
(не показаны 2 промежуточные версии 1 участника)
Строка 28: Строка 28:
 
</latex>
 
</latex>
  
−
'''Привльный ответ: (А)'''
+
'''Правильный ответ: (А)'''
  
 
=== Объяснение ===
 
=== Объяснение ===
Строка 45: Строка 45:
 
*# В модели сравнения можно доказать, что худший случай с временем <m>\(o(n \log n)\)</m> невозможен.
 
*# В модели сравнения можно доказать, что худший случай с временем <m>\(o(n \log n)\)</m> невозможен.
  
−
Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет <m>\( \Theta(n \log n)\)</m>, а для задачи самых дальних соседей — <m>\( \Theta(n)\)</m>, что соответствует:
+
Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет <m>\( \Theta(n \log n)\)</m>, а для задачи самых дальних соседей — <m>\( \Theta(n)\)</m>.
  
−
(A) <m>\( \Theta(n \log n)\)</m> для ближайших соседей и <m>\( \Theta(n)\)</m> для самых дальних соседей.
+
[[Участник:StasFomin|StasFomin]] 09:58, 9 января 2025 (UTC): {{BadTest}}
−
 
+
−
{{question-ok|}}
+
−
 
+
−
{{checkme|[[Участник:Nikitashapovalov|Nikitashapovalov]] 22:38, 8 января 2025 (UTC)}}
+

Текущая версия на 09:58, 9 января 2025

Вопрос: Q32-08c765

Ближайшие соседи: Дан неотсортированный массив из чисел с плавающей точкой. Необходимо найти два из них, которые ближе всего друг к другу по значению.

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

Предположим, что разрешены только следующие операции с данными:

  • Сравнение значений двух элементов массива с целью определения большего из них;
  • Сравнение расстояния между двумя элементами массива (абсолютное значение разности между значениями двух элементов) с расстоянием между двумя другими элементами массива;
  • Перестановка двух элементов массива.

Также предполагается, что каждая разрешённая операция стоит единичную стоимость. Каковы наихудшие (в худшем случае) асимптотические временные сложности алгоритмов, решающих эти две задачи?

Ответы

Правильный ответ: (А)

Объяснение

Исходники — вопрос 32 на 30 странице книги «2011-gre-cs-practice-book.pdf»

Можно сделать следующие наблюдения:

  • Самые дальние соседи
    1. Нужно найти только глобальный минимум и максимум массива.
    2. Поиск минимума и максимума может быть выполнен за время (с одним проходом по массиву).
    3. Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения .
  • Ближайшие соседи
    1. Классический подход состоит в том, чтобы сначала отсортировать массив (за время ), а затем выполнить один линейный проход по отсортированному массиву, чтобы найти минимальную разницу между соседними элементами (время ).
    2. Это дает общее время выполнения .
    3. В модели сравнения можно доказать, что худший случай с временем невозможен.

Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет , а для задачи самых дальних соседей — .

StasFomin 09:58, 9 января 2025 (UTC):

Посмотрите как оформлять тесты. Нет уже сил обьяснять каждому.

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q32&oldid=35583»