2

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

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) 

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

1 ответ 1

7

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

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

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

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.