То, что я думаю, я понимаю.
В худшем случае алгоритм быстрой сортировки выбирает самый большой или самый маленький ключ в списке/массиве для сортировки для каждого рекурсивного вызова (если рекурсивная реализация). Я понимаю, что размер n будет определять как количество рекурсивных вызовов, так и количество сравнений (которые будут уменьшаться на 1 с каждым шагом рекурсии). Итак, мы имеем n + (n-1) + (n-2) + ... + 2 + 1 число примитивных сравнений в целом.Большая временная сложность худшего случая быстрая сортировка?
Что я не понимаю.
Часть, которую я не совсем понимаю, как это O (n^2)? Как я знаю, он равен хотя бы O (n^2) как n + (n-1) + (n-2) + ... + 2 + 1 < n^2, но откуда я знаю, что это не говорит O (п * LOGN)? Должен ли я доказывать этот результат, чтобы безопасно подтвердить, что это O (n^2), или это сразу видно так, как я не вижу? Я думаю, в общем, как мне узнать, что я нашел самую низкую функцию, которая представляет большую сложность времени O.