2011-gre-cs-practice-book.pdf/Q51 — различия между версиями
(→Объяснение) |
|||
| Строка 14: | Строка 14: | ||
=== Объяснение === | === Объяснение === | ||
| − | Для k-упорядоченного массива при сортировке вставками каждый элемент может «съехать» максимум на k позиций от своего итогового места. Когда мы идём по элементам слева направо, чтобы вставить элемент на правильное место, в худшем случае придётся сравнивать его с не более чем k предыдущими элементами. | + | Для <m>k</m>-упорядоченного массива при сортировке вставками каждый элемент может «съехать» максимум на <m>k</m> позиций от своего итогового места. Когда мы идём по элементам слева направо, чтобы вставить элемент на правильное место, в худшем случае придётся сравнивать его с не более чем <m>k</m> предыдущими элементами. |
| − | Таким образом, в каждом из n шагов вставки мы делаем до k сравнений. Суммарно получается порядка kn сравнений. То есть сложность в худшем случае будет | + | Таким образом, в каждом из <m>n</m> шагов вставки мы делаем до <m>k</m> сравнений. Суммарно получается порядка <m>kn</m> сравнений. То есть сложность в худшем случае будет <m>\(\Theta(kn)\)</m>. |
{{question-ok|}} | {{question-ok|}} | ||
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:35, 8 января 2025 (UTC)}} | {{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:35, 8 января 2025 (UTC)}} | ||
Версия 00:40, 9 января 2025
Вопрос: Q51-08c765
Массив, называемый k-упорядоченным, — это почти упорядоченный массив, в котором ни один элемент не находится дальше, чем на k позиций от своего конечного места в отсортированном массиве. Таким образом, 0-упорядоченный массив полностью отсортирован, а любой массив размера n является n-упорядоченным.
Предположим, что A — это k-упорядоченный массив размера n. Если для сортировки A используется сортировка вставками, какова будет сложность по числу сравнений в худшем случае?
Ответы
- (A)
- (B)
- (C)
- (D)
- (E)
Объяснение
Для -упорядоченного массива при сортировке вставками каждый элемент может «съехать» максимум на позиций от своего итогового места. Когда мы идём по элементам слева направо, чтобы вставить элемент на правильное место, в худшем случае придётся сравнивать его с не более чем предыдущими элементами.
Таким образом, в каждом из шагов вставки мы делаем до сравнений. Суммарно получается порядка сравнений. То есть сложность в худшем случае будет .
Задача зарезервирована: Nikitashapovalov 20:35, 8 января 2025 (UTC)