2011-gre-cs-practice-book.pdf/Q51 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q51-08c765 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показано 11 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q51-08c765 == | == Вопрос: Q51-08c765 == | ||
| − | + | Массив, называемый ''k-упорядоченным'', — это почти упорядоченный массив, в котором ни один элемент не находится дальше, чем на ''k'' позиций от своего конечного места в отсортированном массиве. | |
| − | + | Таким образом, 0-упорядоченный массив полностью отсортирован, а любой массив размера ''n'' является n-упорядоченным. | |
| − | + | ||
| − | + | ||
| − | + | Предположим, что A — это k-упорядоченный массив размера n. Если для сортировки A используется сортировка вставками, какова будет сложность по числу сравнений в худшем случае? | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>\(\Theta(k)\)</m> |
| − | ( | + | * Правильный ответ: <m>\(\Theta(kn)\)</m> |
| − | + | * <m>\(\Theta(k^2n)\)</m> | |
| − | * Правильный ответ: | + | * <m>\(\Theta(n \log_k n)\)</m> |
| − | * | + | * <m>\(\Theta(n^2)\)</m> |
| − | * | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|39|51}} | |
| − | {{cstest-source|2011-gre-cs-practice-book.pdf| | + | |
| − | + | Для k-упорядоченного массива при сортировке вставками каждый элемент может «съехать» максимум на k позиций от своего итогового места. Когда мы идём по элементам слева направо, чтобы вставить элемент на правильное место, в худшем случае придётся сравнивать его с не более чем k предыдущими элементами. | |
| − | + | Таким образом, в каждом из n шагов вставки мы делаем до k сравнений. Суммарно получается порядка kn сравнений. То есть сложность в худшем случае будет <m>\(\Theta(kn)\)</m>. | |
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 10:55, 9 января 2025 (UTC)}} | |
| − | + | [[Категория:Sorting]] | |
Текущая версия на 10:55, 9 января 2025
Вопрос: Q51-08c765
Массив, называемый k-упорядоченным, — это почти упорядоченный массив, в котором ни один элемент не находится дальше, чем на k позиций от своего конечного места в отсортированном массиве. Таким образом, 0-упорядоченный массив полностью отсортирован, а любой массив размера n является n-упорядоченным.
Предположим, что A — это k-упорядоченный массив размера n. Если для сортировки A используется сортировка вставками, какова будет сложность по числу сравнений в худшем случае?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 51 на 39 странице книги «2011-gre-cs-practice-book.pdf»
Для k-упорядоченного массива при сортировке вставками каждый элемент может «съехать» максимум на k позиций от своего итогового места. Когда мы идём по элементам слева направо, чтобы вставить элемент на правильное место, в худшем случае придётся сравнивать его с не более чем k предыдущими элементами.
Таким образом, в каждом из n шагов вставки мы делаем до k сравнений. Суммарно получается порядка kn сравнений. То есть сложность в худшем случае будет .