Quais são as características de um

19

Às vezes, é fácil identificar a complexidade de tempo de um algoritmo, examinando-o cuidadosamente. Algoritmos com dois loops aninhados de são obviamente . Algoritmos que explore todas as combinações possíveis de grupos de dois valores são obviamente .N 2 N 2 NNN2N2N

No entanto, não sei como "detectar" um algoritmo com complexidade . Uma implementação de fusão recursiva, por exemplo, é uma. Quais são as características comuns do mergesort ou de outros algoritmos que me dariam uma pista se eu estivesse analisando uma?Θ ( N log N )Θ(NlogN)Θ(NlogN)

Tenho certeza de que há mais de uma maneira pela qual um algoritmo pode ter a complexidade , para que todas e quaisquer respostas sejam apreciadas. Aliás, estou buscando características e dicas gerais, não provas rigorosas.Θ(NlogN)

Barry Fruitman
fonte
6
O(logn) significa árvore.
Pratik Deoghare 25/02
2
@PratikDeoghare: Não necessariamente.
Raphael
3
@ Rafael eu quis dizer principalmente! :)
Pratik Deoghare

Respostas:

17

Seu arquetípico é um algoritmo de dividir e conquistar , que divide (e recombina) o trabalho em tempo linear e se repete sobre as peças. A classificação por mesclagem funciona dessa maneira: gaste tempo dividindo a entrada em duas partes aproximadamente iguais, classifique recursivamente cada peça e gaste tempo combinando as duas metades classificadas.O ( n ) Θ ( n )Θ(nlogn)O(n)Θ(n)

Intuitivamente, continuando a idéia de dividir e conquistar, cada estágio de divisão leva um tempo linear no total, porque o aumento no número de peças a serem divididas corresponde exatamente à diminuição no tamanho das peças, pois o tempo gasto pela divisão é linear. O tempo total de execução é o produto do custo total de um estágio de divisão multiplicado pelo número de estágios de divisão. Como o tamanho das peças é dividido pela metade a cada vez, existem estágios de divisão do , portanto o tempo total de execução é n log ( n ) . (Até uma constante multiplicativa, a base do logaritmo é irrelevante.)log2(n)nlog(n)

Colocando-o nas equações (), uma maneira de estimar o tempo de execução de um algoritmo é expressá-lo recursivamente: T ( n ) = 2 T ( n / 2 ) + Θ ( n ) . É claro que esse algoritmo leva mais que o tempo linear e podemos ver quanto mais dividindo por n : T ( n )T(n)T(n)=2T(n/2)+Θ(n)n Quandondobra,T(n)/naumenta em uma quantidade constante:T(n)/naumenta logaritmicamente, ou seja,T(n)=Θ(nlogn).

T(n)n=T(n/2)n/2+Θ(1)
nT(n)/nT(n)/nT(n)=Θ(nlogn)

Este é um exemplo de um padrão mais geral: o teorema mestre . Para qualquer algoritmo recursivo que divide a sua entrada de tamanho em um pedaços de tamanho n / b e leva um tempo f ( n ) para realizar a divisão e recombinação, o satisfaz tempo de execução T ( n ) = um T ( n / b ) + f ( n ) . Isto conduz a uma forma fechada que depende dos valores de um e b e a forma denan/bf(n)T(n)=aT(n/b)+f(n)ab . Se a = b e f ( n ) = Θ ( n ) , o teorema mestre declara que T ( n ) = Θ ( n log n ) .fa=bf(n)=Θ(n)T(n)=Θ(nlogn)

Gilles 'SO- parar de ser mau'
fonte
1
Resumindo: algoritmos que eliminam frações constantes do espaço de pesquisa por vez exibem termos logarítmicos. Os outros fatores dependem de quanto tempo leva para realizar o desaparecimento.
Raphael
1
exemplo: caso médio quicksort O(nlogn)
vzn 28/02
11

Duas outras categorias de algoritmos que levam :Θ(nlogn)

Algoritmos em que cada item é processado por vez e leva tempo logarítmico para processar cada item (por exemplo, HeapSort ou muitos dos algoritmos de geometria computacional de varredura de avião).

Algoritmos em que o tempo de execução é dominado por uma etapa de pré-processamento de classificação. (Por exemplo, no algoritmo de Kruskal para árvore de abrangência mínima, podemos classificar as arestas por peso como o primeiro passo).

Joe
fonte
Votado para o primeiro parágrafo. O segundo parece redundante, uma vez que os algoritmos de classificação linearitômica que conhecemos são ou dividem e conquistam ou montam. Um exemplo para a primeira categoria é a pesquisa de objetos em uma árvore de pesquisa binária (ou matriz classificada) de tamanho n ; em um nível mais abstrato, que também pode ser visto como dividir e conquistar. nn
Raphael
@ Rafael Eu sei que a classificação é redundante com as categorias de tempos de execução já fornecidas. O ponto é que a classificação às vezes é o "gargalo" e os algoritmos em que, à primeira vista, a questão não é sobre classificação ainda podem ter o tempo de execução, porque a classificação é necessária.
26413 Joe Joe
9

Outra categoria: os algoritmos nos quais a saída possui tamanho e, portanto, Θ ( n log n ) o tempo de execução é linear no tamanho da saída .Θ(nlogn)Θ(nlogn)

Embora os detalhes de tais algoritmos usem frequentemente técnicas de dividir e conquistar, eles não precisam necessariamente. O tempo de execução vem fundamentalmente da pergunta que está sendo feita e, portanto, acho que vale a pena mencionar separadamente.

Isso ocorre nas estruturas de dados baseadas em uma árvore de pesquisa binária aumentada, em que cada nó armazena uma estrutura de dados de tamanho linear para pesquisar sobre as folhas na subárvore desse nó. Tais estruturas de dados surgem frequentemente na pesquisa por faixa geométrica e geralmente são baseadas em um esquema de decomposição . Veja a Pesquisa da Agarwal .

O(nlogn)O(logn)

Joe
fonte
θ(nlogn)
6

O(nlogn)kO(n)O(n)O(n)

Yuval Filmus
fonte
5

Esses são tipicamente algoritmos da variedade "dividir e conquistar", em que o custo de dividir e combinar subsoluções não é "muito grande". Dê uma olhada nesta FAQ para ver que tipos de recorrências causam esse comportamento.

vonbrand
fonte
3

Normalmente, os algoritmos de divisão e conquista renderão complexidade O (N log N).

Brent Hronik
fonte
-1

O(nlogn)

for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

O(n2)

Não posso dar um exemplo concreto de um algoritmo que use esse loop, mas ele aparece frequentemente ao codificar algoritmos personalizados.

Nicolas Miari
fonte
O(nlogn)Θ(n)Θ(1)Θ(|n|)n
O(nlogn)
Além disso, a pergunta original não pedia big-theta.
Nicolas Miari
1
O(nlogn)O(22n)O(almost anything else)Θ(nlogn)O(nlogn)
David Richerby
O(nlogn)O(nlogn)O(nlogn)O(nlogn)
Nicolas Miari