Pergunta

Eu tenho trabalhado através de um recente trabalho de casa Ciência da Computação envolvendo recursão e notação big-O. Eu acredito que eu entendo isso muito bem (certamente não perfeitamente, embora!) Mas há uma questão em particular que está me dando mais problemas. O curioso é que, olhando-o, parece ser a simples mais sobre o trabalho de casa.

Fornecer a melhor taxa de crescimento usando a notação big-Oh para a solução para o seguinte recorrência?

T (1) = 2

T (n) = 2T (n - 1) + 1 para n> 1

E as opções são:

  • O (N log N)
  • O (n ^ 2)
  • O (2 ^ n)
  • O (n ^ n)

Eu entendo que as obras grandes O como um limite superior, para descrever a maior quantidade de cálculos, ou o maior tempo de execução, esse programa ou processo vai demorar. Eu sinto que esta recursão especial deve ser O (n), uma vez que, no máximo, a recursão ocorre apenas uma vez para cada valor de n. Desde que n não está disponível, ou é melhor do que isso, O (nlogn), ou pior, sendo as outras três opções.

Então, minha pergunta é: Por que não é este o (n)

Foi útil?

Solução

Há um par de maneiras diferentes para resolver recorrências: substituição, árvore de recorrência e teorema de mestre. Teorema Mestre não irá funcionar no caso, porque ele não se encaixa no formulário mestre teorema.

Você pode usar os outros dois métodos, mas a maneira mais fácil para este problema é resolvê-lo de forma iterativa.

T (n) = 2T (n-1) + 1 | T (n) = 4T (n-2) + 2 + 1 | T (n) = T8 (n-3) + 4 + 2 + 1 | T (n) = ...

Veja o padrão?

T (n) = 2 n-1 ·T (1) + 2 n-2 + 2 n-3 +. .. + 1 | T (n) = 2 n-1 ·2 + 2 n-2 + 2 n-3 + ... + 1
T (n) = 2 n + 2 n-2 + 2 n-3 + ... + 1

Portanto, o mais apertada ligado é T (2 n ).

Outras dicas

Eu acho que você ter entendido mal a pergunta um pouco. Não pedir-lhe quanto tempo que seria necessário para resolver a recorrência. Ele está pedindo o que o big-O (a assintótica ligado) da própria solução é.

O que você tem a fazer é chegar a uma solução fechada, i. e. a fórmula não-recursiva para T (n), e, em seguida, determinar o que o grande-O de expressão que é.

A questão está pedindo a notação big-Oh para a solução para a recorrência, e não o custo do cálculo da recorrência.

Dito de outra forma: a recorrência produz: 

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

O big-Oh notação melhor descreve a sequência 2, 5, 11, 23, 47, ...

A maneira correta de resolver isso é para resolver as equações de recorrência.

Eu acho que isso vai ser exponencial. Cada incremento de n faz com que o valor a ser duas vezes maior. 

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T (x) seria o tempo de execução do seguinte programa (por exemplo): 

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

Eu acho que isso vai ser exponencial. Cada incremento de n traz o dobro de cálculo.

Não, isso não acontece. Muito pelo contrário:

Considere que para tempo n iterações, ficamos correndo R . Então, para n + 1 iterações vamos obter exatamente R + 1.

Assim, a taxa de crescimento é constante e o tempo total de funcionamento é, de facto O ( n ).

No entanto, acho que a suposição de Dima sobre a questão é certa embora sua solução é excessivamente complicado:

O que você tem a fazer é chegar a uma solução fechada, i. e. a fórmula não-recursiva para T (n), e, em seguida, determinar o que o grande-O de expressão que é.

É suficiente para examinar o tamanho relativo de T ( n ) e T ( n + 1) iterações e determinar a taxa de crescimento relativa. A quantidade obviamente duplas que dá diretamente o crescimento assintótica.

Em primeiro lugar, todas as quatro respostas são piores do que O (n) ... O (n * log n) é mais complexa do que O velho liso (n). Qual é maior: 8 ou 8 * 3, 16 ou 16 * 4, etc ...

Por que a questão real. A solução geral pode, obviamente, ser resolvido em tempo constante, se você não está fazendo a recursão

(T (n) = 2 ^ (n - 1) + 2 ^ (n) - 1), de modo que não é o que eles estão pedindo

.

E como você pode ver, se escrever o código recursivo: 

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

É óbvio que é O (n).

Assim, parece ser uma pergunta mal formulada, e eles provavelmente estão pedindo o crescimento da função em si, não a complexidade do código. Isso é 2 ^ n. Agora vá fazer o resto da sua casa ... e estudar-se sobre O (n * log n)

Calculando uma solução fechada para a recursividade é fácil. Por inspeção, você acho que a solução é 

T(n) = 3*2^(n-1) - 1

Então você provar por indução que este é verdadeiramente uma solução. caso Base: 

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

Indução: 

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

onde a primeira igualdade decorre da definição de recorrência, e o segundo a partir da hipótese indutiva. QED.

3 * 2 ^ (n-1) -. 1 é claramente teta (2 ^ n), por conseguinte, a resposta à direita é a terceira

Para as pessoas que responderam O (n): Eu não poderia concordar mais com Dima. O problema faz não pedir mais apertados limite superior para a complexidade computacional de um algoritmo para calcular T (n) (o que seria agora O (1), desde a sua forma fechada foi fornecido). O problema pede mais apertados limite superior em T (n) em si , e que é o exponencial.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top