Библиотека Go для собеса | вопросы с собеседований

❓ Можно ли добиться от быстрой сортировки времени выполнения O(n log n)

Классическая быстрая сортировка выбирает опорный элемент. Если выбор плохой — например, всегда крайний элемент массива — и массив уже отсортирован (или почти), происходит деградация: один подмассив получает почти все элементы, а другой — почти пустой. Это приводит к дереву рекурсии глубиной n, и итоговая сложность становится O(n²).

Если опорный элемент выбирается случайно, то с высокой вероятностью дерево рекурсии будет сбалансированным. Это даёт среднюю сложность O(n log n), даже на почти отсортированных данных.

Выбор опорного элемента как медианы из первого, среднего и последнего элементов. Существенно снижает вероятность деградации при частично отсортированных массивах.

🐸Библиотека Go для собеса

Please open Telegram to view this post

VIEW IN TELEGRAM

www.tgoop.com/go_interview_lib/839

2.5K viewsedited  May 7 at 18:29

❓ Можно ли добиться от быстрой сортировки времени выполнения O(n log n)

Классическая быстрая сортировка выбирает опорный элемент. Если выбор плохой — например, всегда крайний элемент массива — и массив уже отсортирован (или почти), происходит деградация: один подмассив получает почти все элементы, а другой — почти пустой. Это приводит к дереву рекурсии глубиной n, и итоговая сложность становится O(n²).

Если опорный элемент выбирается случайно, то с высокой вероятностью дерево рекурсии будет сбалансированным. Это даёт среднюю сложность O(n log n), даже на почти отсортированных данных.

Выбор опорного элемента как медианы из первого, среднего и последнего элементов. Существенно снижает вероятность деградации при частично отсортированных массивах.

🐸Библиотека Go для собеса