2011-gre-cs-practice-book.pdf/Q51 — различия между версиями
StasFomin (обсуждение | вклад) |
|||
| Строка 6: | Строка 6: | ||
=== Ответы === | === Ответы === | ||
| − | * | + | * <m>\(\Theta(k)\)</m> |
* Правильный ответ: (B) <m>\(\Theta(kn)\)</m> | * Правильный ответ: (B) <m>\(\Theta(kn)\)</m> | ||
| − | * | + | * <m>\(\Theta(k^2n)\)</m> |
| − | * | + | * <m>\(\Theta(n \log_k n)\)</m> |
| − | * | + | * <m>\(\Theta(n^2)\)</m> |
=== Объяснение === | === Объяснение === | ||
Версия 10:52, 9 января 2025
Вопрос: Q51-08c765
Массив, называемый k-упорядоченным, — это почти упорядоченный массив, в котором ни один элемент не находится дальше, чем на k позиций от своего конечного места в отсортированном массиве. Таким образом, 0-упорядоченный массив полностью отсортирован, а любой массив размера n является n-упорядоченным.
Предположим, что A — это k-упорядоченный массив размера n. Если для сортировки A используется сортировка вставками, какова будет сложность по числу сравнений в худшем случае?
Ответы
- Правильный ответ: (B)
Объяснение
Исходники — вопрос 51 на 39 странице книги «2011-gre-cs-practice-book.pdf»
Для k-упорядоченного массива при сортировке вставками каждый элемент может «съехать» максимум на k позиций от своего итогового места. Когда мы идём по элементам слева направо, чтобы вставить элемент на правильное место, в худшем случае придётся сравнивать его с не более чем k предыдущими элементами.
Таким образом, в каждом из n шагов вставки мы делаем до k сравнений. Суммарно получается порядка kn сравнений. То есть сложность в худшем случае будет .
Решено: Nikitashapovalov 00:44, 9 января 2025 (UTC)