Como eu determino o tempo de execução de uma função recursiva dupla?

15

Tendo em conta qualquer função arbitrariamente dupla recursiva, como calcular o seu tempo de execução?

Por exemplo (em pseudocódigo):

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

Ou algo nesse sentido.

Que métodos poderiam ou deveriam ser usados para determinar algo assim?

    
por if_zero_equals_one 05.07.2011 / 21:14
fonte

6 respostas

11

Você continua mudando sua função. Mas continue escolhendo os que serão executados para sempre sem conversão ...

A recursão se torna complicada, rápida. O primeiro passo para analisar uma função duplamente recursiva proposta é tentar rastreá-la em alguns valores de amostra, para ver o que ela faz. Se seu cálculo entrar em um loop infinito, a função não está bem definida. Se o seu cálculo entrar em uma espiral que continua recebendo números maiores (o que acontece com muita facilidade), provavelmente não está bem definido.

Se traçarmos uma resposta, você tenta chegar a algum padrão ou relação de recorrência entre as respostas. Depois de ter isso, você pode tentar descobrir seu tempo de execução. Descobrir isso pode ser muito, muito complicado, mas temos resultados como o Teorema do Mestre que nos permite descobrir a resposta em muitos casos.

Tenha em atenção que, mesmo com recursão única, é fácil criar funções cujo tempo de execução não saibamos calcular. Por exemplo, considere o seguinte:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

É atualmente desconhecido se esta função é sempre bem definida, quanto mais seu tempo de execução.

    
por 05.07.2011 / 23:11
fonte
5

O tempo de execução desse par particular de funções é infinito porque nenhum retorna sem chamar o outro. O valor de retorno de a é sempre dependente do valor de retorno de uma chamada para b , que sempre chama a ... e isso é conhecido como < em> recursão infinita .

    
por 05.07.2011 / 21:42
fonte
4

O método óbvio é executar a função e medir quanto tempo demora. Isso só lhe diz quanto tempo leva em uma entrada específica, no entanto. E se você não sabe de antemão que a função termina, difícil: não há uma maneira mecânica de descobrir se a função termina - essa é a parada problema e é indecidível.

Encontrar o tempo de execução de uma função é igualmente indecidível, pelo Teorema de Rice . De fato, o teorema de Rice mostra que mesmo decidir se uma função é executada em O(f(n)) time é indecidível.

Portanto, o melhor que você pode fazer em geral é usar sua inteligência humana (que, até onde sabemos, não está limitada pelos limites das máquinas de Turing) e tentar reconhecer um padrão, ou inventar um. Uma maneira típica de analisar o tempo de execução de uma função é transformar a definição recursiva da função em uma equação recursiva em seu tempo de execução (ou um conjunto de equações para funções mutuamente recursivas):

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

O que vem depois? Você agora tem um problema de matemática: você precisa resolver essas equações funcionais. Uma abordagem que geralmente funciona é transformar essas equações em funções inteiras em equações em funções analíticas e usar o cálculo para resolvê-las, interpretando as funções T_a e T_b as gerando funções .

Ao gerar funções e outros tópicos de matemática discretos, recomendo o livro Matemática Concreta , por Ronald Graham, Donald Knuth e Oren Patashnik.

    
por 05.07.2011 / 23:37
fonte
1

Como outros salientaram, analisar a recursão pode ser muito difícil muito rápido. Aqui está outro exemplo de tal coisa: link link é difícil calcular uma resposta e um tempo de execução para eles. Isto é devido a estas funções recursivas reciprocamente tendo uma "forma difícil".

De qualquer forma, vamos ver este exemplo simples:

link

(declare funa funb)
(defn funa [n]
  (if (= n 0)
    0
    (funb (dec n))))
(defn funb [n]
  (if (= n 0)
    0
    (funa (dec n))))

Vamos começar tentando calcular funa(m), m > 0 :

funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.

O tempo de execução é:

R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way

Agora vamos escolher outro exemplo, um pouco mais complicado:

Inspirado pelo link , que é uma boa leitura por si só, vamos analisar: "" "Os números de Fibonacci podem ser interpretado via recursão mútua: F (0) = 1 e G (0) = 1, com F (n + 1) = F (n) + G (n) e G (n + 1) = F (n). " ""

Então, qual é o tempo de execução de F? Nós vamos para o outro lado. Bem, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Agora R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
Não é difícil ver que R (F (m)) = F (m) - p. o número de chamadas de função necessárias para calcular um número de Fibonacci no índice i é igual ao valor de um número de Fibonacci no índice i. Isso pressupõe que adicionar dois números juntos é muito mais rápido do que uma chamada de função. Se este não fosse o caso, então isso seria verdade: R (F (1)) = R (F (0)) + 1 + R (G (0)), e a análise disso teria sido mais complicada, possivelmente sem uma solução de forma fechada fácil.

A forma fechada para a sequência de Fibonacci não é necessariamente fácil de reinventar, para não mencionar alguns exemplos mais complicados.

    
por 06.07.2011 / 01:05
fonte
0

A primeira coisa a fazer é mostrar que as funções que você definiu terminam e para quais valores exatamente. No exemplo que você definiu

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

b só termina por y <= -5 , porque se você conectar qualquer outro valor, você terá um termo no formato b(a(y-1)) . Se você expandir um pouco mais, verá que um termo no formato b(a(y-1)) leva ao termo b(1010) , que leva a um termo b(a(1009)) , o que leva novamente ao termo b(1010) . Isso significa que você não pode inserir nenhum valor em a que não satisfaça x <= -4 , porque se você acabar com um loop infinito, onde o valor a ser computado depende do valor a ser computado. Então, essencialmente, este exemplo tem um tempo de execução constante.

Portanto, a resposta simples é que não há um método geral para determinar o tempo de execução de funções recursivas, porque não existe um procedimento geral que determine se uma função definida recursivamente termina.

    
por 06.07.2011 / 05:17
fonte
-5

Tempo de execução como em Big-O?

Isso é fácil: O (N) - assumindo que existe uma condição de finalização.

A recursão é apenas loop, e um loop simples é O (N) não importa quantas coisas você faça nesse loop (e chamar outro método é apenas mais um passo no loop).

Onde ele ficaria interessante é se você tiver um loop dentro de um ou mais dos métodos recursivos. Nesse caso, você acabaria com algum tipo de desempenho exponencial (multiplicando por O (N) em cada passagem pelo método).

    
por 05.07.2011 / 21:49
fonte