0
Какова наихудшая временная сложность медианы мерседесов (точка опоры определяется медианью медианов, которые берут O (n) время, чтобы найти)?Какова наихудшая временная сложность медианных мерседесов?
A
ответ
2
Примерный алгоритм медианного выбора также может быть использован в качестве стратегии поворота в быстрой сортировке, что дает оптимальный алгоритм, с наихудшей сложностью O (п § п).
Это потому, что алгоритм медианы медианов предотвращает плохое разбиение, которое произойдет в наивной быстрой сортировке на уже отсортированном массиве.
Если я правильно помню свои алгоритмы, я думаю, что это 'O (n^2)'. –
Почему? Медиана медианов обеспечивает хорошие перегородки в каждом случае. –