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

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

Вопрос: Q32-08c765

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

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

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

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

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

Ответы

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

Объяснение

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

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

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

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

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

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

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

• Изучение тестов по Computer Science
• Топик соответствующего чата
• Уже оформленные тесты Категория:Test_Question
• Ну если уж и тогда непонятно — спрашивайте в ТГ группе или лично.

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

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

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