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

Задача зарезервирована: Tiniakov.ad 12:18, 21 декабря 2024 (UTC)

Вопрос: Q35-08c765

Рассмотрим следующий алгоритм, сортирующий массив из n ≥ 2 целых чисел:

1. Если в массиве всего 2 элемента, сравнить их и поменять местами если они в неправильном порядке
2. Иначе, делать следующие шаги по порядку:
   1. Рекурсивно отсортировать первые n-1 элементов массива
   2. Рекурсивно отсортировать последние n-1 элементов массива
   3. Рекурсивно отсортировать первые 2 элемента массива

Какова асимптотическая временная сложность этого алгоритма, измеряемая количеством проведенных сравнений?

Ответы

• Правильный ответ:

Объяснение

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

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

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

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