2011-gre-cs-practice-book.pdf/Q35 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
== Вопрос: Q35-08c765 == | == Вопрос: Q35-08c765 == | ||
| Строка 23: | Строка 21: | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|31|35}} | {{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 вызовов операции сравнения и правильный ответ -- .