Как определить сложность алгоритма сортировки?

Question

Имеется алгоритм сортировки:

def search(a):
    if len(a) < 2:
        return a
    pivot = a[0]
    left = [int(i) for i in a[1:] if i < pivot]
    right = [int(i) for i in a[1:] if i > pivot]
    
    return search(left) + [pivot] + search(right)

Я хочу определить его сложность, не подскажете, как это сделать?

Answer 1

по моему это алгоритм быстрой сортировки, сложность в среднем случае O(nlogn), в худшем случае O(n^2)

в худшем случае в качестве опорного элемента выбирается самый маленький или самый большой элемент и тогда массив каждый раз будет делится на массив длиной 1 и n - 1
в среднем случае массив делится logn раз (то есть примерно пополам) и на каждом делении происходит проверка всех элементов больше или меньше они опорного

также советую в качестве опорного элемента выбирать случайный элемент или средний какой нибудь на случай частично отсортированного массива

БЛОГ НА HUSL

Как определить сложность алгоритма сортировки?

Ответы (1 шт):