2011-gre-cs-practice-book.pdf/Q32 — различия между версиями
(→Ответы) |
(→Ответы) |
||
| Строка 19: | Строка 19: | ||
\hline | \hline | ||
\textbf{Nearest Neighbors} & \textbf{Farthest Neighbors} \\ \hline | \textbf{Nearest Neighbors} & \textbf{Farthest Neighbors} \\ \hline | ||
| − | (A) $\Theta(n \log n)$ & $\Theta(n)$ \\ \hline | + | (A) $\Theta(n \log n)$ & $\Theta(n)$ \\ \hline |
(B) $\Theta(n \log n)$ & $\Theta(n \log n)$ \\ \hline | (B) $\Theta(n \log n)$ & $\Theta(n \log n)$ \\ \hline | ||
(C) $\Theta(n^2)$ & $\Theta(n)$ \\ \hline | (C) $\Theta(n^2)$ & $\Theta(n)$ \\ \hline | ||
| Строка 27: | Строка 27: | ||
\end{center} | \end{center} | ||
</latex> | </latex> | ||
| + | |||
| + | Привльный ответ: (А) | ||
=== Ответы === | === Ответы === | ||
Версия 22:21, 8 января 2025
Содержание
Вопрос: Q32-08c765
Ближайшие соседи: Дан неотсортированный массив из чисел с плавающей точкой. Необходимо найти два из них, которые ближе всего друг к другу по значению.
Самые дальние соседи: Дан неотсортированный массив из чисел с плавающей точкой. Необходимо найти два из них, которые дальше всего друг от друга по значению.
Предположим, что разрешены только следующие операции с данными:
- Сравнение значений двух элементов массива с целью определения большего из них;
- Сравнение расстояния между двумя элементами массива (абсолютное значение разности между значениями двух элементов) с расстоянием между двумя другими элементами массива;
- Перестановка двух элементов массива.
Также предполагается, что каждая разрешённая операция стоит единичную стоимость. Каковы наихудшие (в худшем случае) асимптотические временные сложности алгоритмов, решающих эти две задачи?
Ответы
Привльный ответ: (А)
Ответы
Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так (префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)
- Правильный ответ: тут реально правильный ответ
- неправильный ответ
- еще какой-то неправильный ответ
- еще какой-то неправильный ответ
- еще какой-то неправильный ответ
Если ответы длинные, многострочные, или там графы, используйте способ задания ответов разделами, Но такое очень редко встречается.
Объяснение
Сначала заполните номер страницы с этим вопросом Исходники — вопрос 32 на 30 странице книги «2011-gre-cs-practice-book.pdf»
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а неправильные варианты — неправильны. Тут тоже могут быть полезны ссылки на википедию, решение вами рекуррентных уравнений в sympy.
Задача зарезервирована: Nikitashapovalov 19:54, 8 января 2025 (UTC)