2011-gre-cs-practice-book.pdf/Q51

Ссылки сюда (1) →

Вопрос: Q51-08c765

Массив, называемый k-упорядоченным, — это почти упорядоченный массив, в котором ни один элемент не находится дальше, чем на k позиций от своего конечного места в отсортированном массиве. Таким образом, 0-упорядоченный массив полностью отсортирован, а любой массив размера n является n-упорядоченным.

Предположим, что A — это k-упорядоченный массив размера n. Если для сортировки A используется сортировка вставками, какова будет сложность по числу сравнений в худшем случае?

Ответы

• (A)
• Правильный ответ: (B)
• (C)
• (D)
• (E)

Объяснение

Исходники — вопрос 51 на 39 странице книги «2011-gre-cs-practice-book.pdf»

Для k-упорядоченного массива при сортировке вставками каждый элемент может «съехать» максимум на k позиций от своего итогового места. Когда мы идём по элементам слева направо, чтобы вставить элемент на правильное место, в худшем случае придётся сравнивать его с не более чем k предыдущими элементами.

Таким образом, в каждом из n шагов вставки мы делаем до k сравнений. Суммарно получается порядка kn сравнений. То есть сложность в худшем случае будет . Решено: Nikitashapovalov 00:44, 9 января 2025 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.