Complexidade de classificação de inserção binária para trocas e comparação no melhor caso

Question

Qual poderia ser a complexidade da classificação por inserção binária? E quantas trocas e comparações são feitas?

Podem ser O(n(LG n))comparações, mas não tenho certeza. Para o pior caso, são de fato N^2trocas. Qual é o melhor?

Answer 1

Você pode escrever classificação por inserção binária facilmente aproveitando as funções integradas, como bisect_lefte list.pop(..)e 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

Sobre o pior caso, já que na i-thiteração do loop, realizamos uma busca binária dentro da submatriz A[0..i], com 0<=i<n, que deve realizar log(i)operações, então agora sabemos que temos que inserir um elemento no local i1e o inserimos, mas a inserção significa que temos que empurrar todos os elementos que o seguem uma posição à direita, e isso é, pelo menos, n-ioperações (podem ser mais do que n-ioperações, dependendo do local de inserção). Se somarmos apenas estes dois, obtemos\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(na aproximação de Stirling acima de log(n!)está sendo usado)

Agora a página wiki diz

Como regra geral, pode-se supor que o termo de ordem mais alta em qualquer função dada domina sua taxa de crescimento e, portanto, define sua ordem de tempo de execução

Portanto, acho que a conclusão seria que, no pior caso, a classificação por inserção binária tem O(n^2)complexidade.

Veja também:

• classificação por inserção usando pesquisa binária
• classificação por inserção com pesquisa binária
• análise do tipo de inserção binária
• tipo e complexidade de inserção binária

Em seguida, tentei verificar o desempenho das listas reversa ( n,n-1,n-2,..,1) e alternada ( 0,n-1,1,n-2,2,n-3,...). E eu os ajustei (usando o módulo de crescimento de fósforo ) para diferentes taxas de crescimento, esta parte é apenas uma aproximação. A ordem reversa foi ajustada ao tempo polinomial, e a ordem alternada foi ajustada ao tempo quase-linear

O melhor caso é explicado aqui . Se a lista já estiver ordenada, mesmo que não façamos nenhuma troca, todas as buscas binárias ainda estão sendo realizadas, o que leva a O(n*log(n)).

O código usado aqui está disponível neste repositório.