Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 23

Предположим, что рассмотренные здесь алгоритмы сортируют входные последовательности в порядке возрастания. Если вход уже находится в порядке возрастания, что из следующего является ИСТИНА?

I.   Quicksort runs in Θ(n2) time
II.  Bubblesort runs in Θ(n2) time
III. Mergesort runs in  Θ(n) time
IV.  Insertion sort runs in  Θ(n) time 

(A) только I и II
(B) только I и III
(C) только II и IV
(D) только I и IV

Ответ: (D)
Объяснение: I. Учитывая массив в порядке возрастания, отношение повторения для общего числа сравнений для быстрой сортировки будет
T (n) = T (n-1) + O (n) // алгоритм разбиения примет O (n) сравнений в любом случае.
= O (n ^ 2)

II. Bubble Sort выполняется за Θ (n ^ 2) времени

Если массив находится в порядке возрастания, мы могли бы сделать небольшую модификацию в цикле Bubble Sort Inner for, которая отвечает за пузырение k-го наибольшего элемента до конца в k-й итерации. Всякий раз, когда нет перестановки после завершения внутреннего цикла for пузырьковой сортировки на любой итерации, мы можем объявить, что массив сортируется в случае, если Bubble Sort занимает O (n) время в Best Case.

III. Сортировка слиянием выполняется за время Θ (n)
Сортировка слиянием полагается на парадигму «Разделяй и властвуй» для сортировки массива, и для сортировки слиянием нет такого наихудшего или наилучшего ввода. Для любой последовательности временная сложность будет определяться следующим рекуррентным соотношением:

T (n) = 2T (n / 2) + Θ (n) // Алгоритм слияния на месте займет Θ (n) из-за копирования всего массива.
= Θ (nlogn)

Внутривенно Сортировка вставки выполняется за время Θ (n)

Всякий раз, когда добавляется новый элемент, который будет больше, чем все элементы промежуточного отсортированного подмассива (поскольку данный массив отсортирован), не будет никакого обмена, кроме одного сравнения. В n-1 проходах у нас будет 0 обменов и n-1 сравнений.
Общая сложность времени = O (n) // N-1 Сравнения

Это решение предоставлено Пранджул Ахаджа

////
Для массива, уже отсортированного в порядке возрастания,
Быстрая сортировка имеет сложность Θ (n 2 ) [Худший случай]
Bubblesort имеет сложность Θ (n) [Лучший случай]
Mergesort имеет сложность Θ (n log n) [Любой случай]
Insertsort имеет сложность Θ (n) [Лучший случай]

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 23

0.00 (0%) 0 votes