2011-gre-cs-practice-book.pdf/Q32

Ссылки сюда (1) →

Вопрос: Q32-08c765

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

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

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

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

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

Ответы

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

Объяснение

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

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

• Самые дальние соседи
  1. Нужно найти только глобальный минимум и максимум массива.
  2. Поиск минимума и максимума может быть выполнен за время \( \Theta(n)\) (с одним проходом по массиву).
  3. Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения \( \Theta(n)\).

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

Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет \( \Theta(n \log n)\), а для задачи самых дальних соседей — \( \Theta(n)\), что соответствует:

(A) для ближайших соседей и для самых дальних соседей.

Задача зарезервирована: Nikitashapovalov 19:54, 8 января 2025 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.