Рубрики

Алгоритмы | Сортировка | Вопрос 16

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

Ответ: (Б)
Объяснение: Дерево повторения для сортировки слиянием будет иметь высоту Log (n). И работа O (n ^ 2) будет выполняться на каждом уровне дерева рекуррентности (каждый уровень включает в себя n сравнений, а сравнение занимает O (n) время в худшем случае). Таким образом, временная сложность этой сортировки слиянием будет ,
Тест на этот вопрос

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

Алгоритмы | Сортировка | Вопрос 16

0.00 (0%) 0 votes