2011-gre-cs-practice-book.pdf/Q32 — различия между версиями
(→Ответы) |
|||
| Строка 30: | Строка 30: | ||
Привльный ответ: (А) | Привльный ответ: (А) | ||
| − | |||
| − | |||
| − | |||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|30|32}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Можно сделать следующие наблюдения: | |
| − | + | ||
| − | + | ||
| + | * Самые дальние соседи | ||
| + | *# Нужно найти только глобальный минимум и максимум массива. | ||
| + | *# Поиск минимума и максимума может быть выполнен за время \( \Theta(n)\) (с одним проходом по массиву). | ||
| + | *# Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения \( \Theta(n)\). | ||
| − | + | * Ближайшие соседи | |
| − | + | *# Классический подход состоит в том, чтобы сначала отсортировать массив (за время \( \Theta(n \log n)\)), а затем выполнить один линейный проход по отсортированному массиву, чтобы найти минимальную разницу между соседними элементами (время \(\Theta(n)\)). | |
| − | + | *# Это дает общее время выполнения \( \Theta(n \log n)\). | |
| − | + | *# В модели сравнения (где каждое решение зависит от сравнения) можно доказать, что худший случай с временем \(o(n \log n)\) невозможен. | |
| − | + | ||
| − | + | Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет \( \Theta(n \log n)\), а для задачи самых дальних соседей — \( \Theta(n)\), что соответствует: | |
| − | + | ||
| − | + | ||
| − | </ | + | (A) <m>\( \Theta(n \log n)\)</m> для ближайших соседей и <m>\( \Theta(n)\)</m> для самых дальних соседей. |
{{question-ok|}} | {{question-ok|}} | ||
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 19:54, 8 января 2025 (UTC)}} | {{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 19:54, 8 января 2025 (UTC)}} | ||
Версия 22:32, 8 января 2025
Вопрос: Q32-08c765
Ближайшие соседи: Дан неотсортированный массив из чисел с плавающей точкой. Необходимо найти два из них, которые ближе всего друг к другу по значению.
Самые дальние соседи: Дан неотсортированный массив из чисел с плавающей точкой. Необходимо найти два из них, которые дальше всего друг от друга по значению.
Предположим, что разрешены только следующие операции с данными:
- Сравнение значений двух элементов массива с целью определения большего из них;
- Сравнение расстояния между двумя элементами массива (абсолютное значение разности между значениями двух элементов) с расстоянием между двумя другими элементами массива;
- Перестановка двух элементов массива.
Также предполагается, что каждая разрешённая операция стоит единичную стоимость. Каковы наихудшие (в худшем случае) асимптотические временные сложности алгоритмов, решающих эти две задачи?
Ответы
Привльный ответ: (А)
Объяснение
Исходники — вопрос 32 на 30 странице книги «2011-gre-cs-practice-book.pdf»
Можно сделать следующие наблюдения:
- Самые дальние соседи
- Нужно найти только глобальный минимум и максимум массива.
- Поиск минимума и максимума может быть выполнен за время \( \Theta(n)\) (с одним проходом по массиву).
- Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения \( \Theta(n)\).
- Ближайшие соседи
- Классический подход состоит в том, чтобы сначала отсортировать массив (за время \( \Theta(n \log n)\)), а затем выполнить один линейный проход по отсортированному массиву, чтобы найти минимальную разницу между соседними элементами (время \(\Theta(n)\)).
- Это дает общее время выполнения \( \Theta(n \log n)\).
- В модели сравнения (где каждое решение зависит от сравнения) можно доказать, что худший случай с временем \(o(n \log n)\) невозможен.
Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет \( \Theta(n \log n)\), а для задачи самых дальних соседей — \( \Theta(n)\), что соответствует:
(A) для ближайших соседей и для самых дальних соседей.
Задача зарезервирована: Nikitashapovalov 19:54, 8 января 2025 (UTC)