Рубрики

ВОРОТА | GATE CS 2012 | Вопрос 37

Список из n строк, каждая из которых имеет длину n, сортируется в лексикографическом порядке с использованием алгоритма сортировки слиянием. Наихудшее время выполнения этого вычисления
(A) O (n log n)
(B) O (n 2 log n)
(С) O (n 2 + log n)
(D) O (n 2 )

Ответ: (Б)
Объяснение:

Когда мы сортируем массив из n целых чисел, отношение повторения для общего числа проведенных сравнений будет

T (n) = 2T (n / 2) + (n) где (n) — количество сравнений для объединения 2 отсортированных подмассивов размера n / 2.
= (nlog2n)

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

ВОРОТА | GATE CS 2012 | Вопрос 37

0.00 (0%) 0 votes