Artigos

2.4: Resolvendo Relações de Recorrência


Exemplo ( PageIndex {1} )

Encontre uma relação de recorrência e condições iniciais para (1, 5, 17, 53, 161, 485 ldots text {.} )

Solução

Encontrar a relação de recorrência seria mais fácil se tivéssemos algum contexto para o problema (como a Torre de Hanói, por exemplo). Infelizmente, temos apenas a sequência. Lembre-se de que a relação de recorrência informa como ir dos termos anteriores para os termos futuros. O que está acontecendo aqui? Poderíamos ver as diferenças entre os termos: (4, 12, 36, 108, ldots text {.} ) Observe que eles estão crescendo por um fator de 3. A sequência original também está? (1 cdot 3 = 3 text {,} ) (5 cdot 3 = 15 text {,} ) (17 cdot 3 = 51 ) e assim por diante. Parece que sempre terminamos com 2 a menos do que no próximo período. Aha!

Portanto, (a_n = 3a_ {n-1} + 2 ) é nossa relação de recorrência e a condição inicial é (a_0 = 1 text {.} )


Relações de Recorrência

UMA Relação de recorrência é uma equação na qual cada termo da sequência é definido como uma função dos termos anteriores.

Existem diferentes maneiras de resolver essas relações, vamos examinar:

Resolvendo relações de recorrência por derivação / substituição repetida

A premissa para esse tipo de solução é substituir continuamente a relação de recorrência no lado direito (ou seja, substituir um valor na equação original e, em seguida, derivar uma versão anterior da equação). As várias derivações devem levar a uma forma generalizada da equação que pode ser resolvida por uma restrição de tempo no algoritmo / equação: Por exemplo:

A única substituição disponível neste ponto é substituir n / 2 por n na equação original:

Adicione c a ambos os lados para derivar a equação original:

Agora que outra equação foi derivada, há uma nova substituição que pode ser feita no original: n / 4 para n

Em geral, a equação básica é:

Fazendo uma suposição de que n = 2 k permite:

Resolvendo relações de recorrência por meio do telescópio

A premissa para este tipo de solução é substituir os valores de n, somar os resultados e eliminar os termos semelhantes. Por exemplo:


O método mestre

O método Master é aplicável para resolver recorrências do formulário
$ begin T (n) = aT left ( frac direita) + f (n) fim$
onde $ a ge 0 $ e $ b ge 1 $ são constantes e $ f (n) $ é uma função assintoticamente positiva. Dependendo do valor de $ a, b $ e da função $ f (n) $, o método mestre possui três casos.

  1. Se $ f (n) = O (n ^ < log_b a- epsilon>) $ para alguma constante $ epsilon> 0 $, então $ T (n) = Theta (n ^ < log_b a>) $ .
  2. Se $ f (n) = Theta (n ^ < log_b a>) $, então $ T (n) = Theta (n ^ < log_b a> log n) $.
  3. Se $ f (n) = Omega (n ^ < log_b a + epsilon>) $ para alguma constante $ epsilon> 0 $, e se $ af (n / b) le cf (n) $ para alguma constante $ c 0 $ é uma constante para $ i le i le k $
  4. $ b_i in (0, 1) $ é uma constante para $ 1 le i le k $
  5. $ k ge 1 $ é uma constante e,
  6. $ f (n) $ é uma função não negativa

A solução de recorrência dada em (2) é,
$ T (n) = Theta left (n ^ p left (1 + int_ <1> ^ frac<>

> du right) right) $
Forneceu,
$ sum_^a_ib_i ^ p = 1 text $

Exemplo 1: Considere uma recorrência,
$ T (n) = 2T (n / 4) + 3T (n / 6) + Theta (n log n) $

Para esta recorrência, $ a_1 = 2, b_1 = 1/4, a_2 = 3, b_2 = 1/6, f (n) = n log n $. O valor de $ p $ pode ser calculado como,
$ a_1b_1 ^ p + a_2b_2 ^ p = 2 vezes (1/4) ^ p + 3 vezes (1/6) ^ p = 1 $
$ p = 1 $ satisfaz a equação acima. A solução é
$ begin T (n) & = Theta left (n ^ p left (1 + int_ <1> ^ frac<>

> du right) right)
& = Theta left (n left (1 + int_ <1> ^ frac du right) right)
& = Theta left (n left (1 + frac < log ^ 2n> <2> right) right)
& = Theta (n log ^ 2n)
fim$


Método de substituição de costas

No método de substituição direta, colocamos $ n = 0, 1, 2,… $ na relação de recorrência até ver um padrão. Na substituição reversa, fazemos o oposto, ou seja, colocamos $ n = n, n - 1, n - 2,… $ ou $ n = n, n / 2, n / 4,… $ até vermos o padrão. Depois de ver o padrão, fazemos uma suposição para o tempo de execução e verificamos a suposição. Vamos usar esse método em alguns exemplos.

Considere um exemplo de relação de recorrência fornecido abaixo
$ T (n) = begin 1 & text n = 1 2T left ( frac <2> direita) + n & texto fim$

Dado $ T (n) $, podemos calcular o valor de $ T (n / 2) $ a partir da relação de recorrência acima como
$ T (n / 2) = 2T left ( frac <4> right) + frac<2>$
Agora substituímos novamente o valor de $ T (n / 2) $ em $ T (n) $
$ T (n) = 2 ^ 2T left ( frac<2 ^ 2> right) + 2n $
Nós procedemos de maneira semelhante
$ beginT (n) & = 2 ^ 3T left ( frac <2 ^ 3> right) + 3n
& = 2 ^ 4T left ( frac <2 ^ 4> direita) + 4n
& = 2 ^ kT left ( frac <2 ^ k> right) + kn
fim$
Agora devemos usar a condição de limite (base), ou seja, $ T (1) = 1 $. Para usar a condição de limite, a entidade dentro de $ T () $ deve ser 1, ou seja,
$ frac <2 ^ k> = 1 $
Pegando $ log_2 $ em ambos os lados,
$ n = log_2 n $
A equação (6) torna-se
$ begin
T (n) & = 2 ^ < log_2 n> T left ( frac<2 ^ < log_2 n >> right) + log_2 n.n
& = nT (1) + n log_2 n
& = n log_2 n + n
fim$
A exatidão do tempo de execução acima pode ser comprovada por indução. Coloque $ n = 2, 4, 8, 16,… $ e você pode facilmente verificar se o tempo de execução estimado está realmente correto.

Raramente usamos o método de substituição para frente e para trás nos casos práticos. Existem métodos muito mais sofisticados e rápidos. Mas esses métodos podem ser usados ​​como último recurso quando outros métodos são impotentes para resolver alguns tipos de recorrências.


2.4: Resolvendo Relações de Recorrência

No post anterior, discutimos a análise de loops. Muitos algoritmos são recursivos por natureza. Quando os analisamos, obtemos uma relação de recorrência para a complexidade do tempo. Obtemos o tempo de execução em uma entrada de tamanho n como uma função de n e o tempo de execução em entradas de tamanhos menores. Por exemplo, em Merge Sort, para classificar um determinado array, nós o dividimos em duas metades e repetimos recursivamente o processo para as duas metades. Finalmente mesclamos os resultados. A complexidade de tempo de Merge Sort pode ser escrita como T (n) = 2T (n / 2) + cn. Existem muitos outros algoritmos como Pesquisa Binária, Torre de Hanói, etc.

Existem basicamente três maneiras de resolver as recorrências.

1) Método de Substituição: Fazemos uma estimativa para a solução e, em seguida, usamos a indução matemática para provar que a estimativa está correta ou incorreta.

2) Método da árvore de recorrência: Neste método, desenhamos uma árvore de recorrência e calculamos o tempo gasto por cada nível da árvore. Por fim, somamos o trabalho realizado em todos os níveis. Para desenhar a árvore de recorrência, partimos da recorrência dada e continuamos desenhando até encontrar um padrão entre os níveis. O padrão é normalmente uma série aritmética ou geométrica.

3) Método Mestre:
O Método Mestre é uma forma direta de obter a solução. O método mestre funciona apenas para os seguintes tipos de recorrências ou para recorrências que podem ser transformadas no seguinte tipo.

Existem três casos a seguir:
1. Se f (n) = O (n c) onde c & lt Logba então T (n) = Θ (n Log b a )

2. Se f (n) = Θ (n c) onde c = Logba então T (n) = Θ (n c Log n)

3.Se f (n) = Ω (n c) onde c> Logba então T (n) = Θ (f (n))

Como é que isso funciona?
O método mestre é derivado principalmente do método da árvore de recorrência. Se desenharmos a árvore de recorrência de T (n) = aT (n / b) + f (n), podemos ver que o trabalho realizado na raiz é f (n) e o trabalho realizado em todas as folhas é Θ (nc) onde c é logbuma. E a altura da árvore de recorrência é Logbn

No método da árvore de recorrência, calculamos o trabalho total realizado. Se o trabalho realizado nas folhas for mais polinomialmente, então as folhas são a parte dominante e nosso resultado passa a ser o trabalho realizado nas folhas (Caso 1). Se o trabalho realizado nas folhas e na raiz for assintoticamente igual, nosso resultado será a altura multiplicada pelo trabalho realizado em qualquer nível (Caso 2). Se o trabalho realizado na raiz for assintoticamente maior, nosso resultado será o trabalho realizado na raiz (Caso 3).

Exemplos de alguns algoritmos padrão cuja complexidade de tempo pode ser avaliada usando o Método Mestre
Classificação de mesclagem: T (n) = 2T (n / 2) + Θ (n). Ele cai no caso 2, pois c é 1 e Logba] também é 1. Portanto, a solução é Θ (n Logn)

Pesquisa binária: T (n) = T (n / 2) + Θ (1). Também cai no caso 2, pois c é 0 e Logba também é 0. Portanto, a solução é Θ (Logn)

Notas:
1) Não é necessário que uma recorrência da forma T (n) = aT (n / b) + f (n) possa ser resolvida usando o Teorema Mestre. Os três casos fornecidos têm algumas lacunas entre eles. Por exemplo, a recorrência T (n) = 2T (n / 2) + n / Logn não pode ser resolvida usando o método mestre.

2) Caso 2 pode ser estendido para f (n) = Θ (n c Log k n)
Se f (n) = Θ (n c Log k n) para alguma constante k> = 0 e c = Logba, então T (n) = Θ (n c Log k + 1 n)

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima

Atenção leitor! Não pare de aprender agora. Conheça todos os conceitos importantes de DSA com o Curso individualizado de DSA a um preço acessível ao aluno e esteja pronto para a indústria. Para completar sua preparação de aprender um idioma para DS Algo e muitos mais, consulte Curso de preparação para entrevista completa.


2.4: Resolvendo Relações de Recorrência

O Método da Árvore de Recursão é uma forma de resolver relações de recorrência. Nesse método, uma relação de recorrência é convertida em árvores recursivas. Cada nó representa o custo incorrido em vários níveis de recursão. Para encontrar o custo total, os custos de todos os níveis são somados.

  1. Desenhe uma árvore recursiva para determinada relação de recorrência
  2. Calcule o custo em cada nível e conte o número total de níveis na árvore de recursão.
  3. Conte o número total de nós no último nível e calcule o custo do último nível
  4. Some o custo de todos os níveis na árvore recursiva

Vamos ver como resolver essas relações de recorrência com a ajuda de alguns exemplos:

Questão 1: T (n) = 2T (n / 2) + c

  • Passo 2: Calcule o trabalho realizado ou custo em cada nível e conte o número total de níveis na árvore de recursão

Árvore recursiva com cada nível de custo

Conte o número total de níveis & # 8211

Escolha o caminho mais longo do nó raiz ao nó folha

Tamanho do problema no último nível = n / 2 k

No último nível, o tamanho do problema torna-se 1

Nº total de níveis na árvore recursiva = k +1 = log2(n) + 1

  • Etapa 3: Conte o número total de nós no último nível e calcule o custo do último nível

T (n) = c + 2c + 4c + & # 8212- + (nº de níveis-1) vezes + custo do último nível

= c + 2c + 4c + & # 8212- + log2(n) vezes + Θ (n)

= c (1 + 2 + 4 + & # 8212- + log2(n) vezes) + Θ (n)

1 + 2 + 4 + & # 8212 & # 8211 + log2(n) vezes & # 8211> 2 0 + 2 1 + 2 2 + & # 8212 & # 8211 + log2 (n) vezes & # 8211> Progressão geométrica (G.P.)

= c (n) + Θ (n)


Desse modo, T (n) = Θ (n)

Questão 2: T (n) = T (n / 10) + T (9n / 10) + n

  • Passo 2: Calcule o trabalho realizado ou custo em cada nível e conte o número total de níveis na árvore de recursão

Árvore de recursão com cada nível de custo

Conte o número total de níveis & # 8211

Escolha o caminho mais longo do nó raiz ao nó folha

(9/10) 0 n & # 8211> (9/10) 1 n & # 8211> (9/10) 2 n & # 8211> & # 8230 & # 8230 & # 8230 & # 8211> (9/10) k n

Tamanho do problema no último nível = (9/10) k n

No último nível, o tamanho do problema torna-se 1

(9/10) k n = 1

(9/10) k = 1 / n

k = log10/9(n)

  • Etapa 3: Conte o número total de nós no último nível e calcule o custo do último nível

Atenção leitor! Não pare de aprender agora. Pratique o exame GATE bem antes do exame real com os questionários sobre o assunto e gerais disponíveis em Curso GATE Test Series.


3.2. Quando T (n) = aT (n-1) + f (n)

Isso é um pouco mais complicado, porque conforme os argumentos para os f's diminuem, eles são multiplicados por mais e mais a's. Depois de alguma substituição para trás, não é difícil reconhecer o padrão

Exemplo: T (n) = 2T (n-1) + n. Então, a partir da fórmula

Isso acaba sendo uma soma bastante dolorosa de resolver exatamente, mas podemos razoavelmente supor que está em algum lugar entre 2 n e 2 n n, e tentar adivinhar-mas-verificar para reduzir ainda mais o intervalo.


Resolvendo Relações Não Lineares

  • O teorema acima é ótimo se você tiver uma recorrência linear homogênea.
    • & hellip com raízes distintas.
    • E o teorema relacionado no texto pode lidar com equações características com raízes repetidas.
    • Suponha que ignoremos a parte não linear e apenas olhemos para a parte homogênea: [h_n = c_1h_ + c_2h_ + cdots + c_kh_,.]
    • Podemos resolver isso e obter uma fórmula para ().
    • Se tivermos sorte, poderemos encontrar uma solução para () para algum condições iniciais, mas talvez não aquelas em que estamos interessados
    • Podemos usar o teorema anterior (ou apenas adivinhar e provar) que as soluções para (h_n = 3h_) estão na forma (h_n = d cdot 3 ^).
    • Se estivermos dispostos a aceitar quaisquer condições iniciais, podemos ser capazes de obter uma solução particular ().
    • Poderíamos supor que pode haver uma solução linear na forma (p_n = cn + d ) para algumas constantes (c, d ).
    • Estaríamos certos. Existe tal solução iff para todos (n & gt 1 ): [ begin p_n & amp = 3p_ + 2n cn + d & amp = 3 (c (n-1) + d) + 2n cn + d & amp = 3cn-3c + 3d + 2n 0 & amp = (2c + 2) n + (2d-3c) ,. fim] Isso é verdadeiro para todos os (n ) iff (2c + 2 = 0 ) e (2d-3c = 0 ). Resolvendo isso, obtemos (c = -1 ) e (d = -3 / 2 ).
    • Temos uma solução para a recorrência: (p_n = -n-3/2 ).
    • Esta não é realmente uma solução útil: estamos interessados ​​em (a_1 = 3 ) e não é isso que (p_1 ) é. Temos as condições iniciais erradas.

    Teorema: Para uma relação de recorrência na forma [a_n = c_1a_ + c_2a_ + cdots + c_ka_ + F (n) ,, ] se tivermos uma solução para a parte linear homogênea () (conforme descrito acima), e uma solução particular (), então todas as soluções para a recorrência estão na forma ().

    Prova: Suponha que temos qualquer solução para a recorrência original: (). Nós sabemos isso () também é uma solução: [a_n = c_1a_ + c_2a_ + cdots + c_ka_ + F (n) p_n = c_1p_ + c_2p_ + cdots + c_kp_ + F (n) ]

    Subtraindo-os, obtemos [a_n-p_n = c_1 (a_-p_) + c_2 (a_-p_) + cdots + c_k (a_-p_)] Desse modo, () é uma solução para a parte homogênea, ().

    Portanto, qualquer solução () pode ser escrito no formato () para alguma solução para a recorrência homogênea. ∎

    • O teorema acima nos diz que todas as soluções para a recorrência se parecem com (a_n = d cdot 3 ^-n-3/2 ).
    • Só temos que preencher (d ): [ begin a_1 & amp = 3 d cdot 3 ^ <1> -1-3 / 2 & amp = 3 d & amp = 11/6 ,. fim]
    • Finalmente temos (a_n = 11/6 cdot 3 ^-n-3/2 ).
    • A parte homogênea disso é (h_n = 2h_). Podemos adivinhar, mas vamos usar o teorema.
    • A equação característica para esta recorrência é (r-2 = 0 ) que tem solução (r = 2 ). Portanto, as soluções estão na forma (h_n = d cdot2 ^ n ).
    • Para uma solução particular, adivinhe que (p_n = c cdot 3 ^ n ) para algum (c ). Podemos confirmar a estimativa encontrando uma constante (c ). Para fazer isso, substituímos na recorrência: [ begin p_n & amp = 2p_+ 3 ^ n c cdot 3 ^ n & amp = 2 (c cdot 3 ^) + 3 ^ n c (3 ^ n-2 cdot 3 ^) & amp = 3 ^ n c (3-2) & amp = 3 ^ n / 3 ^ c & amp = 3 ,. fim]
    • Temos uma solução particular (para nenhuma condição inicial particular) de (p_n = 3 ^).
    • Agora podemos satisfazer (a_n ) para nossa condição inicial, uma vez que todas as soluções para () estão no formato [ begin a_n & amp = d2 ^ n + 3 ^ 5 = a_1 & amp = d2 ^ 1 + 3 ^ 2 5 & amp = 2d + 3 d & amp = 2 ,. fim]
    • Portanto, (a_n = 2 ^+ 3^).
    • A parte homogênea tem equação característica (r ^ 2-5r-6 = 0 ), então raízes (r_1 = 6, r_2 = -1 ).
    • Portanto, as soluções estão na forma (h_n = d_1 6 ^ n + d_2 (-1) ^ n ).
    • Para uma solução particular, devemos encontrar algo na forma (p_n = c cdot 7 ^ n ): [ begin p_n = c cdot 7 ^ n & amp = 5c cdot 7 ^+ 6c cdot 7 ^+ 7 ^ n c cdot 7 ^ 2 & amp = 5c cdot 7 ^ 1 + 6c cdot 7 ^ 0 + 7 ^ 2 0 & amp = 49/8 ,. fim]
    • Portanto, temos (p_n = frac <49> <8> cdot 7 ^ n ).
    • Do teorema, [a_n = d_1 6 ^ n + d_2 (-1) ^ n + tfrac <49> <8> cdot 7 ^ n ,. ]
    • Substituindo (a_0 ) e (a_1 ), obtemos [1 = d_1 + d_2 + tfrac <49> <8> text 6 = 6d_1-d_2 + tfrac <343> <8> , , d_1 = -6 text d_2 = tfrac <7> <8> ,. ]
    • Assim, temos uma solução: [a_n = -6 cdot 6 ^ n- tfrac <7> <8> cdot (-1) ^ n + tfrac <49> <8> cdot 7 ^ n = tfrac <1> <8> left (-8 cdot 6 ^ - 7 (-1) ^ n + 7 ^direito) ,.]
    • Eu definitivamente não teria pensado nisso sem o teorema para ajudar.

    4. O Teorema Mestre

    O Teorema Mestre fornece soluções assintóticas instantâneas para muitas recorrências da forma T (n) = aT (n / b) + f (n), que se aplicam a todos os valores de n (não apenas potências de b). É baseado na aplicação da análise da seção anterior a várias famílias amplas de funções f, e então estendendo os resultados usando um argumento de monotonicidade para valores de n que não são potências de b. Aqui, esboçamos a prova, consulte o Apêndice B do LevitinBook para um argumento mais detalhado.

    Se f (n) = 0, então a recorrência é simplesmente T (n) = aT (n / b). Isso tem solução T (n) = n log [b] a T (1) = Θ (n log [b] a). (Exemplo: T (n) = 4T (n / 2) tem solução Θ (n lg 4) = Θ (n²).) Classificamos diferentes casos do Teorema Mestre com base em como f (n) se compara a esta solução padrão.

    Assumimos que T (1) = Θ (1) do começo ao fim.

    Suponha que f (x) = x c. Então a i f (n / b i) = a i n c / b ic = n c (a / b c) i. A soma é então uma série geométrica com razão (a / b c), e seu comportamento depende criticamente se (a / b c) é menor que 1, igual a 1 ou maior que 1.

    Se (a / b c) for menor que 1, então Sigmai = 0 ao infinito n c (a / b c) i = n c / (1- (a / b c)) = O (n c). Este caso surge quando log (a / b c) = log a - c log b é menor que zero, o que ocorre precisamente quando c & gt log a / log b = logb uma. Portanto, se f (n) = nc, o termo f (n) na soma domina o resto da soma e o n log [b] um termo, e obtemos T (n) = Θ (f (n)) . Se f (n) é Omega (nc), mas satisfaz o requisito técnico adicional de que af (n / b) & lt = (1-delta) f (n) para todo n e algum delta fixo & gt 0, então o argumento da série geométrica ainda funciona com fator (1-delta), e ainda temos T (n) = Θ (f (n)). Isso cobre o caso em que f (n) = Omega (n log [b] a + épsilon).

    Se (a / b c) é igual a 1, então todos os termos da soma são iguais, e o total é f (n) logb n. Neste caso c = logb a, então f (n) = n log [b] a e f (n) logb n domina (apenas) o termo T (1). Uma versão estendida dessa análise mostra que a solução é T (n) = Θ (f (n) log n) quando f (n) = Θ (n log [b] a).

    Finalmente, se (a / b c) for maior que 1, temos uma série geométrica cuja soma é proporcional ao seu último termo, que pode se mostrar assintoticamente menor que o termo T (1). Este caso fornece T (n) = Θ (n log [b] a) para qualquer f (n) = O (n log [b] a - épsilon).

    Esses três casos não cobrem todas as possibilidades (considere T (n) = 2T (n / 2) + n log n), mas eles lidarão com a maioria das recorrências dessa forma que você provavelmente encontrará.


    Isso parece muito próximo da resposta certa.

    Quando $ k = lceil ln (n) / ln (7) rceil $, $ n le 7 ^ k $, então $ A ( lceil n / 7 ^ k rceil) = 1 $.

    Colocando isso em sua equação, $ A (n) = 4 ^ k + 4 ^ k lfloor n / 7 ^ k rfloor ^ 2. +4 lfloor n / 7 rfloor ^ 2 + n ^ 2 $.

    Para obter um limite superior, uma vez que $ lfloor x rfloor le x le lceil x rceil & lt x + 1 $, $ 4 ^ k & lt 4 ^ <1+ ln (n) / ln (7)> = 4n ^ < ln (4) / ln (7)> ​​& lt 4n $ so $ A (n) & lt 4n + n ^ 2 (4 ^ k / 7 ^ k +. + 4/7 + 1) & lt 4n + n ^ 2 / (1-4 / 7) & lt 4n + 7 n ^ 2/3 $.

    Nesse caso, a série que multiplica $ n ^ 2 $ converge.

    Tente resolver isso com o 4 e o 7 trocados, de modo que $ A () = 7A ( lpiso rfloor) + n ^ 2 $.


    Assista o vídeo: Relações de recorrência - An = 5An-1 - 6An-2 - Exercício resolvido (Outubro 2021).