Prove a complexidade de um algoritmo genérico

Question

Prove a complexidade de um algoritmo genérico

#1 resposta do (5 votos)

5

Sou novo na teoria da complexidade e estou tentando provar um fato.

Então, vamos considerar um algoritmo T que recebe na entrada um inteiro n.

Esse algoritmo tem uma complexidade de tempo para n = 1: θ (1) e para n > 1: 2T (n / 2) + θ (n).

Eu preciso provar que o algoritmo T (n) tem complexidade θ (n log (n)). Eu tentei provar isso com indução matemática, mas nada parece funcionar:

n = 1 -> θ(1)

n = 2 -> 2T(2/2)+θ(2) = 2T(1) + θ(2) = 2θ(1)+θ(2).

n = 3 -> 2T(3/2)+θ(3) = ??

Esta abordagem está correta? Existe uma maneira melhor de entender isso?

complexity time

por Madix 11.03.2016 / 19:54

fonte

1 resposta

Tags complexity time

O agrupamento / filtro de itens deve estar na camada ViewModel ou View? As substituições dos roteadores Node.js e Zend são para seqüências de consulta?

score 5 · Accepted Answer

Esta instância específica pode ser resolvida facilmente desenhando como a função T (n) recursiva é calculada. Cada chamada para T (n) tem um custo de θ (n) mais duas vezes o custo de metade do tamanho do problema.

 T(n) = ...

0:                 θ(n)
                  /   \
1:          θ(n/2)     θ(n/2)
            / \           / \
2:     θ(n/4) θ(n/4) θ(n/4) θ(n/4)
        / \       ⋰⋱  ⋰⋱  ⋰⋱
3: θ(n/16) θ(n/16) ⋯ ⋯  ⋯  ⋯  ⋯ ⋯
   ⋰⋱       ⋰⋱
  θ(1) θ(1)  ⋯  ⋯

Cada nível tem duas vezes o número de termos do que o nível anterior. A árvore inteira é log ₂ n níveis profundos. Então, qual é a soma de todos os nós nesta árvore? Podemos descrevê-lo como a soma

2⁰·θ(n/2⁰) + 2¹·θ(n/2¹) + 2²·θ(n/2²) + ⋯ + 2^{(log₂ n)}·θ(1)
= 2⁰·θ(n/2⁰) + 2¹·θ(n/2¹) + 2²·θ(n/2²) + ⋯ + n·θ(n/n)
= Σ_{i = 0 ... log₂n} 2ⁱ·θ(n/2ⁱ)
= Σ_{i = 0 ... log₂n} θ(n)
= log₂(n) · θ(n)
= θ(n · log n)

(Nota: isso pressupõe que a · θ (b · n) = θ (a · b · n) é óbvia, o que tecnicamente eu teria que mostrar em uma prova rigorosa.)

No entanto, esses cálculos são impraticáveis no caso geral. Portanto, normalmente aplicamos o Teorema Mestre que nos dá a complexidade se o tempo de execução recursivo da forma T (n) = a · T (n / b) + f (n) corresponde a um padrão específico. Aqui a = 2, b = 2, f (n) = θ (n).

Com o Teorema Mestre, o caso corresponde onde c = log _b a = 1 e f (n) = θ (n ^c · log ^k n) com k = 0. Isso nos diz que T (n) = θ (n ^c · log ^{k + 1} n) = θ (n · log n). Assim, os dois caminhos chegam à mesma solução, mas o Teorema do Mestre é mais geral e também mais simples, porque só precisamos combinar a estrutura da nossa função recursiva para o tempo de execução com três padrões conhecidos.

Sua abordagem por indução não é satisfatória, porque você não está executando nenhuma etapa de indução . Geralmente, mostramos que a propriedade de indução deve ser mantida para n + 1 se ela for para n, portanto, é correto se ela também é válida para qualquer n conhecido (por exemplo, n = 1). Isto é excessivamente desconfortável de se fazer aqui, então seria melhor provar que uma propriedade vale para 2n se ela for para n. Deixarei isto como um exercício para o leitor;) mas gostaria de salientar que tal indução tecnicamente apenas provaria isso para potências de 2 em vez de todos n, e um argumento adicional seria necessário para generalizar isso.