#python #python-3.x #algorithm #time-complexity #quicksort
#python #python-3.x #алгоритм #сложность по времени #быстрая сортировка
Вопрос:
def partition(A, l, r):
p = A[l]
stack = A[l]
A[l] = A[r]
A[r] = stack
s = l
for i in range(l, r):
if A[i] <= p:
stack2 = A[i]
A[i] = A[s]
A[s] = stack2
s = 1
stack3 = A[s]
A[s] = A[r]
A[r] = stack3
return s
def quicksort(A, l, r):
if l < r:
q = partition(A, l, r)
quicksort(A, l, q - 1)
quicksort(A, q 1, r)
return A
Я написал алгоритм быстрой сортировки «возможно», как я заметил здесь, временная сложность разбиения составляла O (n) из-за цикла for, также сложность быстрой сортировки, по-видимому, составляет не менее O (n). Вопрос: как возможно, чтобы весь код имел общую временную сложность O (nlogn).
Комментарии:
1. Что вы получаете
O(nlogn)?2. потому что у вас есть подзадача, которая равна O (n), но вы должны выполнить ее несколько раз.
3. Будьте осторожны, когда выражаете все о некоторых
n, не говоря, чтоnесть. Рекурсивные вызовы выполняются для подмассива, длина которого короче исходного массива. Сложность одного вызоваpartitionравна O(n), где n — длина вызываемого раздела подмассива, а не длина всего массива. Например, если вы вызываете раздел k раз для подмассивов длиной 1, то общая сложность этих k вызовов составляет всего O (k) .4. @JohnColeman «Средняя временная сложность быстрой сортировки равна O (N log (N))» Я прочитал это на этом сайте — iq.opengenus.org .
5. Но — вы не сказали «сложность среднего случая», вы сказали, что «сложность по времени» полностью остановлена, что по умолчанию означает сложность наихудшего случая.
Ответ №1:
Ваша функция сортировки — нет O(nlogn) . В худшем случае вы выполняете O(n) рекурсивные вызовы.
В качестве простого теста:
def test(n):
nums = list(reversed(range(n)))
return sum(quicksort(nums,0,n-1))
Затем, например, test(1100) запускает:
RecursionError: maximum recursion depth exceeded in comparison
Чего бы не произошло, если бы вы вызывали partition только log(n) раз.
С другой стороны,
import random
def test2(n):
nums = list(range(n))
random.shuffle(nums)
return sum(quicksort(nums,0,n-1))
хорошо работает даже для таких вызовов, как test2(100000) , так что у вас средняя O(nlogn) сложность. Это легко подтвердить численно, но трудно доказать. Смотрите https://en.wikipedia.org/wiki/Quicksort для доказательства.
Ответ №2:
Вы разбиваете на 2 каждого уровня, пока не получите отдельные элементы. Разделение и сравнение, что делает временную сложность. Вы проводите n сравнения на каждом уровне, и вы будете разделять log2(n) время.
В худшем случае ваш массив уже отсортирован, и вы будете разбивать n раз и все равно делать n сравнений на каждом уровне.
