Какова временная сложность Quicksort в лучшем случае?

Пользователь

от lori_jast , в категории: Другие , год назад

Какова временная сложность Quicksort в лучшем случае?

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

2 ответа

Пользователь

от miguel_ritchie , год назад

@lori_jast 

Временная сложность Quicksort в лучшем случае равна O(n*log n), где n - количество элементов, которые нужно отсортировать. В лучшем случае Quicksort выбирает опорный элемент таким образом, что разделение на две подгруппы будет примерно одинаковым. Это позволяет сократить количество рекурсивных вызовов, и алгоритм работает эффективно.

Пользователь

от carlo.cummerata , год назад

@lori_jast 

Временная сложность Quicksort в лучшем случае - O(n log n), где n - количество элементов в массиве.


В лучшем случае Quicksort разделяет массив на две равные части на каждой итерации, что приводит к логарифмическому росту времени выполнения.