Início / coding / Perguntas / 79351047
Accepted
pepper
Asked: 2025-01-13 10:10:06 +0800 CST

Como encontrar uma relação de recorrência dado um pedaço de código com 3 entradas

  • 772
ALGO(A,s,d)
    m=d-s+1
    if m>=2 then
        q=⌊m/2⌋
        return 2ALGO(A, s, s+q-1) + 3ALGO(A, s+q, d);
    else
        return 1
    endif

Eu tenho esse pedaço de código e preciso encontrar a relação de recorrência em função de n. O problema afirma que o algoritmo é inicialmente chamado com ALGO(A, 1, n). A é um array de tamanho n, se dsão inteiros, qé a função de chão de m/2.

A solução que encontrei foi:

T(n) = 1 if n<2

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1) if n>=2.

Meu raciocínio foi que if s=1e d=nentão m=n, q=⌊n/2⌋e na primeira chamada recursiva eu ​​tenho s=1e d=⌊n/2⌋então m=⌊n/2⌋, para a segunda chamada s=s+q=1+⌊n/2⌋ d=nentão m=⌈n/2⌉então T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1)porque dentro do if eu calculo qqual custa 1. Eu não sei se a solução que eu criei está correta ou não e eu não sei como resolver isso. Para a resolução eu não sei se eu posso dizer que T(⌊n/2⌋) + T(⌈n/2⌉) = T(n).

algorithm

1 respostas

  1. Best Answer

    A relação de recorrência que você forneceu está correta, embora o caso base também deva ter θ(1): O valor de 𝑇(1) não é o valor retornado (1), mas o trabalho (complexidade de tempo) necessário para retorná-lo, que é θ(1):

          𝑇(1) = θ(1)

          𝑇(𝑛) = 𝑇(⌊𝑛/2⌋) + 𝑇(⌈𝑛/2⌉) + θ(1)

    Você não pode pular para a identidade 𝑇(⌊𝑛/2⌋) + 𝑇(⌈𝑛/2⌉) = 𝑇(𝑛), porque essa é apenas a notação espelhada do caso recursivo sem o termo θ(1), mas antes de descartar esse termo θ(1), você provavelmente deve mostrar por que pode fazer isso.

    Uma das maneiras de abordar isso é observar que a árvore de recorrência é uma árvore binária completa. Por exemplo, para 𝑛=11, podemos representar essa árvore binária da seguinte forma, mostrando apenas os valores dos parâmetros 𝑠 e 𝑑:

    
                _______1,11________
               /                   \
          ___1,5__               __6,11__
         /        \             /        \
       1,2        3,5         6,8         9,11
      /   \      /   \       /   \       /    \
    1,1   2,2  3,3   4,5   6,6   7,8   9,9   10,11
                    /   \       /   \       /     \
                  4,4   5,5   7,7   8,8  10,10   11,11

    As folhas desta árvore representam os casos base onde return 1é executado, enquanto os nós internos representam os casos onde duas chamadas recursivas são executadas.

    Cada aresta representa uma chamada recursiva.

    É claro que o caso base é executado para quando 𝑠 é igual a 𝑑 e para cada valor possível de 𝑠 entre 1 e 𝑛. Então há 𝑛 folhas. Em qualquer árvore binária completa, o número de nós internos é um a menos que o número de folhas, então isso significa que a árvore tem 2𝑛−1 nós e 2𝑛−2 arestas. Cada nó e cada aresta representam complexidade θ(1), então no total o algoritmo tem uma complexidade de tempo de θ(𝑛).

    Em outras palavras: como o número de nós internos é da mesma ordem que o número de folhas, você pode deixar de fora o termo θ(1) do caso recursivo.

    • 0

relate perguntas