Relação de recorrência

Question

Por que a relação de recorrência do algoritmo fatorial recursivo é isso?

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

Por que não é isso?

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

Colocando valores de N, isto é, 1,2,3,4 ...... A segunda relação de recorrência se mantém (os fatoriais são calculados corretamente) e não a primeira.

Answer 1

Esta pergunta é muito confusa ... sua primeira fórmula não é fatorial. É simplesmente t (n) = n + 1, para todos n. O fatorial de n é o produto dos primeiros n números inteiros positivos: fatorial (1) = 1. Fatorial (n) = n * Fatorial (n-1). Sua segunda fórmula está essencialmente correta.

Answer 2

Parece que t (n) é a relação de recorrência do complexidade do tempo do algoritmo fatorial recursivo, assumindo multiplicação de tempo constante. Talvez você tenha interpretado mal sua fonte?

Answer 3

Geralmente usamos a relação de recorrência Para encontrar a complexidade do tempo do algoritmo.

---

Aqui, a função t (n) não é realmente para calcular o valor de um fatorial, mas está falando sobre a complexidade do tempo do algoritmo fatorial.

---

Significa para encontrar um fatorial de n, será necessário mais 1 operação que o fatorial de N-1 (ou seja, t (n) = t (n-1) +1) e assim por diante.

---

Portanto, a relação de recorrência correta para um algoritmo fatorial recursivo é t (n) = 1 para n = 0 t (n) = 1+t (n-1) para n> 0, não é que você mencionou posteriormente.

---

como a recorrência da torre de hanói é t (n) = 2t (n-1) +1 para n> 0;

Answer 4

Presumo que você tenha informações ruins. A segunda relação de recorrência que você cita é o correto, como você observou. O primeiro apenas gera os números naturais.

Answer 5

Onde você encontrou o primeiro? Está completamente errado.

Ele só vai adicionar 1 cada vez, seja qual for o valor.

Answer 6

O que ele colocou não foi a recursão fatorial, mas a complexidade do tempo dela.
Supondo que este seja o pseudocódigo para essa recorrência:

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)

• Estou assumindo que a eliminação da recuperação da cauda não está envolvida.

A linha 2 e 3 custa um tempo constante, C1 e C2.
A linha 4 também custa um tempo constante. No entanto, ele chama fatorial (n-1) que levará algum tempo t (n-1). Além disso, o tempo necessário para multiplicar fatorial (n-1) por n pode ser ignorado quando t (n-1) é usado.
O tempo para toda a função é apenas a soma: t (n) = c1 + c2 + t (n-1).
Isso, na notação Big-O, é reduzido para t (n) = 1 + t (n-1).

Isso é, como Diam apontou, é uma recursão plana, portanto, seu tempo de execução deve ser O (n). Sua complexidade espacial será enorme.

Answer 7

T (n) = t (n-1) + 1 é a equação de recorrência correta para fatorial de n. Esta equação dá tempo para calcular o fatorial de n não valor do fatorial de n.

Answer 8

Primeiro, você precisa encontrar uma operação básica e, para este exemplo, é multiplicação. A multiplicação acontece uma vez em cada recursão. Então t (n) = t (n-1) +1 Esta +1 é uma operação básica (Mutliplication para este exemplo) t (n-1) é a próxima chamada de recursão.

Answer 9

Tl; dr: a resposta para sua pergunta realmente depende de que sequência Sua relação de recorrência é definindo. Isto é, seja a sequência T_n em sua pergunta representa a função fatorial ou O custo do tempo de execução da computação da função fatorial^X.

---

A função fatorial

o recursivo definição do fatorial de n, f_n, é:

f_n = n • f_N-1 por n> 0 com f₀ = 1.

Como você pode ver, a equação acima é realmente um Relação de recorrência, já que é um equação que, juntamente com o termo inicial (ou seja, f₀ = 1), recursivamente define a seqüência (ou seja, a função fatorial, f_n).

---

Modelando o custo do tempo de execução da computação do fatorial

Agora, vamos encontrar um modelo por representar o custo do tempo de execução de calcular o fatorial de n. Vamos ligar T_n a custo de tempo de execução de computação f_n.

Olhando para a definição acima da função fatorial f_n, seu custo de tempo de execução T_n consistirá no custo do tempo de execução da computação f_N-1 (ou seja, esse custo é T_N-1) além do custo do tempo de execução da execução da multiplicação entre n e f_N-1. A multiplicação é alcançada em tempo constante. Portanto, poderíamos dizer isso T_n = T_N-1 + 1.

No entanto, qual é o valor de T₀? T₀ representa o custo do tempo de execução da computação f₀. Desde o valor de f₀ é inicialmente conhecido por definição, o custo do tempo de execução para computação f₀ é realmente constante. Portanto, poderíamos dizer que T₀ = 1.

Finalmente, o que obtemos é:

T_n = T_N-1 + 1 por n> 0 com T₀ = 1.

Esta equação acima também é um Relação de recorrência. No entanto, o que ele define (junto com o termo inicial) é uma sequência que modela o custo do tempo de execução da computação da função fatorial.

---

^X_{Levando em consideração como a sequência em sua relação de recorrência é chamada (ou seja, Tn), Acho que provavelmente representa o último, ou seja, O custo do tempo de execução da computação da função fatorial.}