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

Текущая версия на 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: Вообще для алгоритмов такой термин почти не используется (концептуально оно странненькое), ну максимум можно нагуглить какие-то редкие упоминания, ну раз мы тут сами его определили, то можно этот вопрос и оставить.