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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 8 промежуточных версий 1 участника)
Строка 28: Строка 28:
 
</latex>
 
</latex>
  
−
Привльный ответ: (А)
+
'''Правильный ответ: (А)'''
−
 
+
  
 
=== Объяснение ===
 
=== Объяснение ===
Строка 38: Строка 37:
 
* Самые дальние соседи   
 
* Самые дальние соседи   
 
*# Нужно найти только глобальный минимум и максимум массива.   
 
*# Нужно найти только глобальный минимум и максимум массива.   
−
*# Поиск минимума и максимума может быть выполнен за время \( \Theta(n)\) (с одним проходом по массиву).   
+
*# Поиск минимума и максимума может быть выполнен за время <m>\( \Theta(n)\)</m> (с одним проходом по массиву).   
−
*# Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения \( \Theta(n)\).
+
*# Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения <m>\( \Theta(n)\)</m>.
  
 
* Ближайшие соседи
 
* Ближайшие соседи
−
*# Классический подход состоит в том, чтобы сначала отсортировать массив (за время \( \Theta(n \log n)\)), а затем выполнить один линейный проход по отсортированному массиву, чтобы найти минимальную разницу между соседними элементами (время \(\Theta(n)\)).   
+
*# Классический подход состоит в том, чтобы сначала отсортировать массив (за время <m>\( \Theta(n \log n)\)</m>), а затем выполнить один линейный проход по отсортированному массиву, чтобы найти минимальную разницу между соседними элементами (время <m>\(\Theta(n)\)</m>).   
−
*# Это дает общее время выполнения \( \Theta(n \log n)\).   
+
*# Это дает общее время выполнения <m>\( \Theta(n \log n)\)</m>.   
−
*# В модели сравнения (где каждое решение зависит от сравнения) можно доказать, что худший случай с временем \(o(n \log n)\) невозможен.
+
*# В модели сравнения можно доказать, что худший случай с временем <m>\(o(n \log n)\)</m> невозможен.
−
 
+
−
Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет \( \Theta(n \log n)\), а для задачи самых дальних соседей — \( \Theta(n)\), что соответствует:
+
  
−
(A) <m>\( \Theta(n \log n)\)</m> для ближайших соседей и <m>\( \Theta(n)\)</m> для самых дальних соседей.
+
Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет <m>\( \Theta(n \log n)\)</m>, а для задачи самых дальних соседей — <m>\( \Theta(n)\)</m>.
  
−
{{question-ok|}}
+
[[Участник:StasFomin|StasFomin]] 09:58, 9 января 2025 (UTC): {{BadTest}}
−
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 19:54, 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»