2011-gre-cs-practice-book.pdf/Q35 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
== Вопрос: Q35-08c765 == | == Вопрос: Q35-08c765 == | ||
| − | + | Рассмотрим следующий алгоритм, сортирующий массив из n ≥ 2 целых чисел: | |
| − | + | # Если в массиве всего 2 элемента, сравнить их и поменять местами если они в неправильном порядке | |
| − | + | # Иначе, делать следующие шаги по порядку: | |
| − | + | ## Рекурсивно отсортировать первые n-1 элементов массива | |
| + | ## Рекурсивно отсортировать последние n-1 элементов массива | ||
| + | ## Рекурсивно отсортировать первые 2 элемента массива | ||
| − | + | Какова асимптотическая временная сложность этого алгоритма, измеряемая количеством проведенных сравнений? | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | |||
| − | |||
| − | * | + | * <m>\Theta(n\log{n})</m> |
| − | * | + | * <m>\Theta(n^2)</m> |
| − | * | + | * <m>\Theta(n^3)</m> |
| − | * | + | * Правильный ответ: <m>\Theta(2^n)</m> |
| − | * | + | * <m>\Theta(3^n)</m> |
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|31|35}} | |
| − | + | ||
| + | Напишем реализацию алгоритма на C: | ||
| + | <code-c> | ||
| + | void sort(int* ar, int sz) | ||
| + | { | ||
| + | if (sz == 2) | ||
| + | { | ||
| + | // сравнить и свапнуть если надо | ||
| + | return; | ||
| + | } | ||
| − | + | sort(ar, sz-1); | |
| − | + | sort(ar+1, sz-1); | |
| − | + | sort(ar, 2); | |
| − | + | } | |
| − | + | </code-c> | |
| − | + | Заметим, что каждый вызов функции sort (за исключением случая когда sz == 2) создает еще 2 вызова той же функции sort всегда с одинаковым sz. При этом каждый вызов функции sort в конце концов приводит к вызову операции сравнения. Следовательно получаем следующую цепочку вызовов функции: f(n) - 2*f(n-1) - 4*f(n-2) - ... - 2^n-2*f(2), следовательно в итоге получается 2^n вызовов операции сравнения и правильный ответ -- <m>\Theta(2^n)</m>. | |
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 12:49, 21 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Решить через sympy]] | |
| + | [[Категория:Sorting]] | ||
Текущая версия на 12:49, 21 декабря 2024
Вопрос: Q35-08c765
Рассмотрим следующий алгоритм, сортирующий массив из n ≥ 2 целых чисел:
- Если в массиве всего 2 элемента, сравнить их и поменять местами если они в неправильном порядке
- Иначе, делать следующие шаги по порядку:
- Рекурсивно отсортировать первые n-1 элементов массива
- Рекурсивно отсортировать последние n-1 элементов массива
- Рекурсивно отсортировать первые 2 элемента массива
Какова асимптотическая временная сложность этого алгоритма, измеряемая количеством проведенных сравнений?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 35 на 31 странице книги «2011-gre-cs-practice-book.pdf»
Напишем реализацию алгоритма на C:
void sort(int* ar, int sz) { if (sz == 2) { // сравнить и свапнуть если надо return; } sort(ar, sz-1); sort(ar+1, sz-1); sort(ar, 2); }
Заметим, что каждый вызов функции sort (за исключением случая когда sz == 2) создает еще 2 вызова той же функции sort всегда с одинаковым sz. При этом каждый вызов функции sort в конце концов приводит к вызову операции сравнения. Следовательно получаем следующую цепочку вызовов функции: f(n) - 2*f(n-1) - 4*f(n-2) - ... - 2^n-2*f(2), следовательно в итоге получается 2^n вызовов операции сравнения и правильный ответ -- .