2019-gate-computer-science-and-it-practice.pdf/Q10-alg3 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q10-alg3-31d68c == <blockquote> Вопрос из «Algorithms Test 3» где-то со страницы 233. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | == Вопрос: Верные утверждения о сортировках == | ||
| + | Рассмотрим следующие утверждения: | ||
| + | * Пусть n — это число элементов в массиве | ||
| + | * В процессе сортировки массива происходит порядка <m>O(\log n)</m> уровней | ||
| + | * На каждом уровне происходит порядка <m>O(n)</m> действий | ||
| − | + | Для какого алгоритма сортировки все утверждения являются верными? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | + | * Сортировка кучей | |
| − | + | * Правильный ответ: Сортировка слиянием | |
| − | + | * Сортировка выбором | |
| − | * Правильный ответ: | + | * Сортировка пузырьком |
| − | * | + | |
| − | * | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | < | + | Сортировка слиянием является устойчивой, в любом случае происходит порядка <m>O(\log n)</m> разбиений. На каждом разбиении получается порядка <m>O(n)</m> сравнений. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|233|10}} |
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 10:10, 25 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Sorting]] |
Текущая версия на 10:10, 25 декабря 2024
Вопрос: Верные утверждения о сортировках
Рассмотрим следующие утверждения:
- Пусть n — это число элементов в массиве
- В процессе сортировки массива происходит порядка уровней
- На каждом уровне происходит порядка действий
Для какого алгоритма сортировки все утверждения являются верными?
Ответы
- Сортировка кучей
- Правильный ответ: Сортировка слиянием
- Сортировка выбором
- Сортировка пузырьком
Объяснение
Сортировка слиянием является устойчивой, в любом случае происходит порядка разбиений. На каждом разбиении получается порядка сравнений.
Исходники — вопрос 10 на 233 странице книги «2019-gate-computer-science-and-it-practice.pdf»