2001-gre-vs-practice.pdf/Q52 — различия между версиями
Илья52 (обсуждение | вклад) |
Илья52 (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
Сортировка выбором: Всегда имеет время выполнения <m>\mathcal{O}(n^2)</m>, независимо от порядка данных. | Сортировка выбором: Всегда имеет время выполнения <m>\mathcal{O}(n^2)</m>, независимо от порядка данных. | ||
| − | + | Сортировка Шелла: Время выполнения зависит от выбранной последовательности шагов, но в среднем может достигать <m>\mathcal{O}(n \log n)</m>. В худшем случае может быть <m>\mathcal{O}(n^2)</m> в зависимости от реализации. | |
Таким образом, алгоритм с наименьшим временем выполнения, зависимым от первоначального порядка ввода, — это сортировка слиянием, так как его время выполнения всегда составляет <m>\mathcal{O}(n \log n)</m>. | Таким образом, алгоритм с наименьшим временем выполнения, зависимым от первоначального порядка ввода, — это сортировка слиянием, так как его время выполнения всегда составляет <m>\mathcal{O}(n \log n)</m>. | ||
Версия 11:20, 7 января 2025
Решено: илья52 11:12, 7 января 2025 (UTC)
Задача зарезервирована: илья52 19:05, 22 декабря 2024 (UTC)
Какой из следующих алгоритмов сортировки имеет время выполнения, НАИМЕНЕЕ зависящее от первоначального порядка ввода?
Ответы
- Сортировка вставками
- Быстрая сортировка
- Правильный ответ: Сортировка слиянием
- Сортировка выбором
- Сортировка Шелла
Объяснение
Исходники — вопрос 52 на 39 странице книги «2001-gre-vs-practice.pdf»
Сортировка вставками: В лучшем случае, когда данные уже отсортированы, имеет время выполнения . В худшем случае (когда данные отсортированы в обратном порядке) — .
Быстрая сортировка: В среднем случае имеет время выполнения , но в худшем случае (если выбор опорного элемента неудачен) — . Однако, в лучшем случае также может быть .
Сортировка слиянием: Всегда имеет время выполнения , независимо от первоначального порядка данных.
Сортировка выбором: Всегда имеет время выполнения , независимо от порядка данных.
Сортировка Шелла: Время выполнения зависит от выбранной последовательности шагов, но в среднем может достигать . В худшем случае может быть в зависимости от реализации.
Таким образом, алгоритм с наименьшим временем выполнения, зависимым от первоначального порядка ввода, — это сортировка слиянием, так как его время выполнения всегда составляет .