Список из 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) время в худшем случае). Таким образом, временная сложность этой сортировки слиянием будет ,
Тест на этот вопрос
Рекомендуемые посты:
- Алгоритмы | Сортировка | Вопрос 10
- Алгоритмы | Сортировка | Вопрос 20
- Алгоритмы | Сортировка | Вопрос 18
- Алгоритмы | Сортировка | Вопрос 17
- Алгоритмы | Сортировка | Вопрос 3
- Алгоритмы | Сортировка | Вопрос 4
- Алгоритмы | Сортировка | Вопрос 23
- Алгоритмы | Сортировка | Вопрос 5
- Алгоритмы | Сортировка | Вопрос 14
- Алгоритмы | Сортировка | Вопрос 6
- Алгоритмы | Сортировка | Вопрос 23
- Алгоритмы | Сортировка | Вопрос 12
- Алгоритмы | Сортировка | Вопрос 13
- Алгоритмы | Сортировка | вопрос 2
- Алгоритмы | Сортировка | Вопрос 23
0.00 (0%) 0 votes