2001-gre-vs-practice.pdf/Q52 — различия между версиями
Илья52 (обсуждение | вклад) |
Илья52 (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{reserve-task|[[Участник:Илья52|илья52]] 19:05, 22 декабря 2024 (UTC)}}== Вопрос: Q52-e5724f == | {{reserve-task|[[Участник:Илья52|илья52]] 19:05, 22 декабря 2024 (UTC)}}== Вопрос: Q52-e5724f == | ||
| − | + | Какой из следующих алгоритмов сортировки имеет время выполнения, НАИМЕНЕЕ зависящее от первоначального | |
| − | + | порядка ввода? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | === Ответы === | |
| − | + | ||
| − | |||
| − | |||
| − | + | * Сортировка вставками | |
| − | + | * Быстрая сортировка | |
| + | * Правильный ответ: Сортировка слиянием | ||
| + | * Сортировка выбором | ||
| + | * Сортировка Шелла | ||
| − | === | + | === Объяснение === |
| − | + | {{cstest-source|2001-gre-vs-practice.pdf|39|52}} | |
| − | + | ||
| − | + | Сортировка вставками: В лучшем случае, когда данные уже отсортированы, имеет время выполнения <m>\bigO{n}</m>. В худшем случае (когда данные отсортированы в обратном порядке) — O(n²). | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Быстрая сортировка: В среднем случае имеет время выполнения O(n log n), но в худшем случае (если выбор опорного элемента неудачен) — O(n²). Однако, в лучшем случае также может быть O(n log n). | |
| − | + | ||
| − | + | ||
| + | 3. Merge sort (Сортировка слиянием): Всегда имеет время выполнения O(n log n), независимо от первоначального порядка данных. | ||
| − | + | 4. Selection sort (Сортировка выбором): Всегда имеет время выполнения O(n²), независимо от порядка данных. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | 5. Shellsort: Время выполнения зависит от выбранной последовательности шагов, но в среднем может достигать O(n log n). В худшем случае может быть O(n^(3/2)) или даже O(n²) в зависимости от реализации. | |
| − | + | ||
| − | + | ||
| − | + | Таким образом, алгоритм с наименьшим временем выполнения, зависимым от первоначального порядка ввода, — это Merge sort, так как его время выполнения всегда составляет O(n log n). | |
{{question-ok|}} | {{question-ok|}} | ||
[[Категория:Надо не забыть выбрать тему]] | [[Категория:Надо не забыть выбрать тему]] | ||
Версия 11:00, 7 января 2025
Задача зарезервирована: илья52 19:05, 22 декабря 2024 (UTC)
Какой из следующих алгоритмов сортировки имеет время выполнения, НАИМЕНЕЕ зависящее от первоначального порядка ввода?
Ответы
- Сортировка вставками
- Быстрая сортировка
- Правильный ответ: Сортировка слиянием
- Сортировка выбором
- Сортировка Шелла
Объяснение
Исходники — вопрос 52 на 39 странице книги «2001-gre-vs-practice.pdf»
Сортировка вставками: В лучшем случае, когда данные уже отсортированы, имеет время выполнения . В худшем случае (когда данные отсортированы в обратном порядке) — O(n²).
Быстрая сортировка: В среднем случае имеет время выполнения O(n log n), но в худшем случае (если выбор опорного элемента неудачен) — O(n²). Однако, в лучшем случае также может быть O(n log n).
3. Merge sort (Сортировка слиянием): Всегда имеет время выполнения O(n log n), независимо от первоначального порядка данных.
4. Selection sort (Сортировка выбором): Всегда имеет время выполнения O(n²), независимо от порядка данных.
5. Shellsort: Время выполнения зависит от выбранной последовательности шагов, но в среднем может достигать O(n log n). В худшем случае может быть O(n^(3/2)) или даже O(n²) в зависимости от реализации.
Таким образом, алгоритм с наименьшим временем выполнения, зависимым от первоначального порядка ввода, — это Merge sort, так как его время выполнения всегда составляет O(n log n).