2001-gre-vs-practice.pdf/Q52 — различия между версиями
Материал из DISCOPAL
Илья52 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
Какой из следующих алгоритмов сортировки имеет время выполнения, НАИМЕНЕЕ зависящее от первоначального | Какой из следующих алгоритмов сортировки имеет время выполнения, НАИМЕНЕЕ зависящее от первоначального | ||
порядка ввода? | порядка ввода? | ||
=== Ответы === | === Ответы === | ||
| − | |||
| − | |||
* Сортировка вставками | * Сортировка вставками | ||
* Быстрая сортировка | * Быстрая сортировка | ||
| Строка 16: | Строка 12: | ||
{{cstest-source|2001-gre-vs-practice.pdf|39|52}} | {{cstest-source|2001-gre-vs-practice.pdf|39|52}} | ||
| − | Сортировка вставками: В лучшем случае, когда данные уже отсортированы, имеет время выполнения <m>\mathcal{O}(n)</m>. В худшем случае (когда данные отсортированы в обратном порядке) | + | ;Сортировка вставками: В лучшем случае, когда данные уже отсортированы, имеет время выполнения <m>\mathcal{O}(n)</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>, но в худшем случае (если выбор опорного элемента неудачен) | + | ;Сортировка слиянием: Всегда имеет время выполнения <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>. В худшем случае может быть <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>. |
| − | {{question-ok|}} | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 14:51, 7 января 2025 (UTC)}} |
| − | [[Категория: | + | [[Категория:Sorting]] |
Текущая версия на 14:51, 7 января 2025
Какой из следующих алгоритмов сортировки имеет время выполнения, НАИМЕНЕЕ зависящее от первоначального порядка ввода?
Ответы
- Сортировка вставками
- Быстрая сортировка
- Правильный ответ: Сортировка слиянием
- Сортировка выбором
- Сортировка Шелла
Объяснение
Исходники — вопрос 52 на 39 странице книги «2001-gre-vs-practice.pdf»
- Сортировка вставками
- В лучшем случае, когда данные уже отсортированы, имеет время выполнения . В худшем случае (когда данные отсортированы в обратном порядке) — .
- Быстрая сортировка
- В среднем случае имеет время выполнения , но в худшем случае (если выбор опорного элемента неудачен) — . Однако, в лучшем случае также может быть .
- Сортировка слиянием
- Всегда имеет время выполнения , независимо от первоначального порядка данных.
- Сортировка выбором
- Всегда имеет время выполнения , независимо от порядка данных.
- Сортировка Шелла
- Время выполнения зависит от выбранной последовательности шагов, но в среднем может достигать . В худшем случае может быть в зависимости от реализации.
Таким образом, алгоритм с наименьшим временем выполнения, зависимым от первоначального порядка ввода, — это сортировка слиянием, так как его время выполнения всегда составляет .