2011-gre-cs-practice-book.pdf/Q42 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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}}

Версия 15:25, 19 декабря 2024

Задача зарезервирована: Ydanyok 15:20, 19 декабря 2024 (UTC)

== Вопрос: Q42-08c765 ==

Реальный коэффициент готовности алгоритма к работе в реальном времени (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»

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q42&oldid=34177»