2011-gre-cs-practice-book.pdf/Q42 — различия между версиями
Ydanyok (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | == Вопрос: Q42-08c765 == | |
| + | Реальный коэффициент готовности алгоритма к работе в реальном времени (real-time readiness ratio, RTR) можно определить, как отношение среднего времени выполнения алгоритма к худшему времени выполнения. | ||
| − | |||
Какой из следующих алгоритмов имеет коэффициент RTR, наиболее близкий к 0? | Какой из следующих алгоритмов имеет коэффициент RTR, наиболее близкий к 0? | ||
| Строка 13: | Строка 13: | ||
=== Объяснение === | === Объяснение === | ||
| + | |||
| + | 1. Сортировка пузырьком (Bubble Sort): | ||
| + | - Среднее время: <m>O(n^2)</m> | ||
| + | - Худшее время: <m>O(n^2)</m> | ||
| + | - Коэффициент RTR: <m>\frac{n^2}{n^2} = 1</m> | ||
| + | |||
| + | 2. Пирамидальная сортировка (Heap Sort): | ||
| + | - Среднее время: <m>O(n \log n)</m> | ||
| + | - Худшее время: <m>O(n \log n)</m> | ||
| + | - Коэффициент RTR: <m>\frac{n \log n}{n \log n} = 1</m> | ||
| + | |||
| + | 3. Сортировка вставкой (Insertion Sort): | ||
| + | - Среднее время: <m>O(n^2)</m> | ||
| + | - Худшее время: <m>O(n^2)</m> | ||
| + | - Коэффициент RTR: <m>\frac{n^2}{n^2} = 1</m> | ||
| + | |||
| + | 4. Слияние-сортировка (Merge Sort): | ||
| + | - Среднее время: <m>O(n \log n)</m> | ||
| + | - Худшее время: <m>O(n \log n)</m> | ||
| + | - Коэффициент RTR: <m>\frac{n \log n}{n \log n} = 1</m> | ||
| + | |||
| + | 5. Быстрая сортировка (Quick Sort): | ||
| + | - Среднее время: <m>O(n \log n)</m> | ||
| + | - Худшее время: <m>O(n^2)</m> | ||
| + | - Коэффициент RTR: <m>\frac{n \log n}{n^2}</m> | ||
| + | |||
{{cstest-source|2011-gre-cs-practice-book.pdf|36|42}} | {{cstest-source|2011-gre-cs-practice-book.pdf|36|42}} | ||
| + | [[Участник:StasFomin|StasFomin]]: Вообще для алгоритмов такой термин почти не используется (концептуально оно странненькое), ну максимум можно нагуглить [http://fakecineaste.blogspot.com/2012/10/an-algorithms-real-time-readiness-ratio.html какие-то редкие упоминания], ну раз мы тут сами его определили, то можно этот вопрос и оставить. | ||
| + | |||
| + | {{question-ok|[[Участник:StasFomin|StasFomin]] 22:31, 19 декабря 2024 (UTC)}} | ||
| − | + | [[Категория:Sorting]] | |
Текущая версия на 22:31, 19 декабря 2024
Вопрос: Q42-08c765
Реальный коэффициент готовности алгоритма к работе в реальном времени (real-time readiness ratio, RTR) можно определить, как отношение среднего времени выполнения алгоритма к худшему времени выполнения.
Какой из следующих алгоритмов имеет коэффициент RTR, наиболее близкий к 0?
Ответы
- Правильный ответ: Быстрая сортировка
- Сортировка слиянием
- Сортировка вставками
- Пирамидальная сортировка
- Сортировка пузырьком
Объяснение
1. Сортировка пузырьком (Bubble Sort):
- Среднее время: - Худшее время: - Коэффициент RTR:
2. Пирамидальная сортировка (Heap Sort):
- Среднее время: - Худшее время: - Коэффициент RTR:
3. Сортировка вставкой (Insertion Sort):
- Среднее время: - Худшее время: - Коэффициент RTR:
4. Слияние-сортировка (Merge Sort):
- Среднее время: - Худшее время: - Коэффициент RTR:
5. Быстрая сортировка (Quick Sort):
- Среднее время: - Худшее время: - Коэффициент RTR:
Исходники — вопрос 42 на 36 странице книги «2011-gre-cs-practice-book.pdf»
StasFomin: Вообще для алгоритмов такой термин почти не используется (концептуально оно странненькое), ну максимум можно нагуглить какие-то редкие упоминания, ну раз мы тут сами его определили, то можно этот вопрос и оставить.