Сложность сортировки двоичной вставки для свопов и сравнения в лучшем случае

Question

В чем может быть сложность сортировки двоичной вставкой? А сколько производится свопов и сравнений?

Это могут быть O(n(LG n))сравнения, но я не уверен. В худшем случае это действительно N^2свопы. А как насчет лучшего?

Answer 1

Вы можете легко написать двоичную сортировку вставкой, используя встроенные функции, такие как bisect_leftи list.pop(..)и list.insert(..):

def bininssort(L):
    n = len(L)
    i,j=0,0
    for i in range(1,n):
        j=i-1
        x=L.pop(i)
        i1=bisect_left(L,x,0,j+1)
        L.insert(i1,x)
    return L

О худшем случае, так как при i-thитерации цикла, мы выполняем бинарный поиск внутри подрешетки A[0..i], с 0<=i<n, что следует принимать log(i)операции, так что мы теперь знаем , что мы должны вставить элемент на месте , i1и мы вставим его, но вставка означает, что мы должны сдвинуть все элементы, следующие за ней, на одну позицию вправо, и это, по крайней мере, n-iоперации (в n-iзависимости от места вставки это может быть больше, чем операций). Если суммировать только эти два, мы получим\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(в приведенном выше приближении Стирлинга в log(n!)настоящее время используется)

Теперь на вики-странице написано

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

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

Смотрите также:

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

Затем я попытался проверить, как он работает в списках reversed ( n,n-1,n-2,..,1) и alternating ( 0,n-1,1,n-2,2,n-3,...). И я приспособил их (используя модуль matchgrowth ) к разным темпам роста, эта часть является всего лишь приближением. Обратный порядок был подогнан к полиномиальному времени, а чередующийся порядок был приспособлен к квазилинейному времени.

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

Используемый здесь код доступен в этом репозитории.