2011-gre-cs-practice-book.pdf/Q32 — различия между версиями
Материал из DISCOPAL
(→Вопрос: Q32-08c765) |
StasFomin (обсуждение | вклад) |
||
| (не показано 17 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Вопрос: Q32-08c765 == | == Вопрос: Q32-08c765 == | ||
| − | < | + | Ближайшие соседи: Дан неотсортированный массив из <m>n</m> чисел с плавающей точкой. Необходимо найти два из них, которые ближе всего друг к другу по значению. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Самые дальние соседи: Дан неотсортированный массив из <m>n</m> чисел с плавающей точкой. Необходимо найти два из них, которые дальше всего друг от друга по значению. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | Самые дальние соседи: Дан неотсортированный массив из | + | |
Предположим, что разрешены только следующие операции с данными: | Предположим, что разрешены только следующие операции с данными: | ||
| − | + | * Сравнение значений двух элементов массива с целью определения большего из них; | |
| − | + | * Сравнение расстояния между двумя элементами массива (абсолютное значение разности между значениями двух элементов) с расстоянием между двумя другими элементами массива; | |
| − | + | * Перестановка двух элементов массива. | |
Также предполагается, что каждая разрешённая операция стоит единичную стоимость. Каковы наихудшие (в худшем случае) асимптотические временные сложности алгоритмов, решающих эти две задачи? | Также предполагается, что каждая разрешённая операция стоит единичную стоимость. Каковы наихудшие (в худшем случае) асимптотические временные сложности алгоритмов, решающих эти две задачи? | ||
=== Ответы === | === Ответы === | ||
| − | < | + | <latex> |
| − | + | \begin{center} | |
| − | + | \begin{tabular}{|c|c|c|} | |
| − | + | \hline | |
| − | + | \textbf{Nearest Neighbors} & \textbf{Farthest Neighbors} \\ \hline | |
| − | + | (A) $\Theta(n \log n)$ & $\Theta(n)$ \\ \hline | |
| − | + | (B) $\Theta(n \log n)$ & $\Theta(n \log n)$ \\ \hline | |
| − | + | (C) $\Theta(n^2)$ & $\Theta(n)$ \\ \hline | |
| − | + | (D) $\Theta(n^2)$ & $\Theta(n \log n)$ \\ \hline | |
| − | + | (E) $\Theta(n^2)$ & $\Theta(n^2)$ \\ \hline | |
| − | + | \end{tabular} | |
| − | + | \end{center} | |
| + | </latex> | ||
| + | '''Правильный ответ: (А)''' | ||
=== Объяснение === | === Объяснение === | ||
| − | |||
{{cstest-source|2011-gre-cs-practice-book.pdf|30|32}} | {{cstest-source|2011-gre-cs-practice-book.pdf|30|32}} | ||
| − | + | Можно сделать следующие наблюдения: | |
| + | |||
| + | * Самые дальние соседи | ||
| + | *# Нужно найти только глобальный минимум и максимум массива. | ||
| + | *# Поиск минимума и максимума может быть выполнен за время <m>\( \Theta(n)\)</m> (с одним проходом по массиву). | ||
| + | *# Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения <m>\( \Theta(n)\)</m>. | ||
| − | + | * Ближайшие соседи | |
| − | + | *# Классический подход состоит в том, чтобы сначала отсортировать массив (за время <m>\( \Theta(n \log n)\)</m>), а затем выполнить один линейный проход по отсортированному массиву, чтобы найти минимальную разницу между соседними элементами (время <m>\(\Theta(n)\)</m>). | |
| − | + | *# Это дает общее время выполнения <m>\( \Theta(n \log n)\)</m>. | |
| + | *# В модели сравнения можно доказать, что худший случай с временем <m>\(o(n \log n)\)</m> невозможен. | ||
| − | </ | + | Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет <m>\( \Theta(n \log n)\)</m>, а для задачи самых дальних соседей — <m>\( \Theta(n)\)</m>. |
| − | + | [[Участник:StasFomin|StasFomin]] 09:58, 9 января 2025 (UTC): {{BadTest}} | |
| − | + | ||
Текущая версия на 09:58, 9 января 2025
Вопрос: Q32-08c765
Ближайшие соседи: Дан неотсортированный массив из чисел с плавающей точкой. Необходимо найти два из них, которые ближе всего друг к другу по значению.
Самые дальние соседи: Дан неотсортированный массив из чисел с плавающей точкой. Необходимо найти два из них, которые дальше всего друг от друга по значению.
Предположим, что разрешены только следующие операции с данными:
- Сравнение значений двух элементов массива с целью определения большего из них;
- Сравнение расстояния между двумя элементами массива (абсолютное значение разности между значениями двух элементов) с расстоянием между двумя другими элементами массива;
- Перестановка двух элементов массива.
Также предполагается, что каждая разрешённая операция стоит единичную стоимость. Каковы наихудшие (в худшем случае) асимптотические временные сложности алгоритмов, решающих эти две задачи?
Ответы
Правильный ответ: (А)
Объяснение
Исходники — вопрос 32 на 30 странице книги «2011-gre-cs-practice-book.pdf»
Можно сделать следующие наблюдения:
- Самые дальние соседи
- Нужно найти только глобальный минимум и максимум массива.
- Поиск минимума и максимума может быть выполнен за время (с одним проходом по массиву).
- Таким образом, задача нахождения самых дальних соседей имеет оптимальное худшее время выполнения .
- Ближайшие соседи
- Классический подход состоит в том, чтобы сначала отсортировать массив (за время ), а затем выполнить один линейный проход по отсортированному массиву, чтобы найти минимальную разницу между соседними элементами (время ).
- Это дает общее время выполнения .
- В модели сравнения можно доказать, что худший случай с временем невозможен.
Следовательно, правильный ответ это тот, где для задачи ближайших соседей время составляет , а для задачи самых дальних соседей — .
StasFomin 09:58, 9 января 2025 (UTC):
Посмотрите как оформлять тесты. Нет уже сил обьяснять каждому.
- Изучение тестов по Computer Science
- Топик соответствующего чата
- Уже оформленные тесты Категория:Test_Question
- Ну если уж и тогда непонятно — спрашивайте в ТГ группе или лично.