Come determino il tempo di esecuzione di una doppia funzione ricorsiva?

Continui a cambiare la tua funzione. Ma continua a raccogliere quelli che dureranno per sempre senza conversione ..

La ricorsione diventa complicata, veloce. Il primo passo per analizzare una funzione doppiamente ricorsiva proposta è provare a tracciarlo su alcuni valori campione, per vedere cosa fa. Se il tuo calcolo entra in un ciclo infinito, la funzione non è ben definita. Se il tuo calcolo entra in una spirale che continua a ottenere numeri più grandi (cosa che avviene molto facilmente), probabilmente non è ben definito.

Se la traccia di una risposta dà una risposta, allora provi a trovare qualche schema o relazione di ricorrenza tra le risposte. Una volta che hai, puoi provare a capire il suo runtime. Capirlo può essere molto, molto complicato, ma abbiamo risultati come il teorema Master che ci permettono di capire la risposta in molti casi.

Attenzione, anche con la ricorsione singola, è facile trovare funzioni il cui runtime non sappiamo come calcolare. Ad esempio, considera quanto segue:

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

È attualmente sconosciuto se questa funzione è sempre ben definita, per non parlare del suo tempo di esecuzione.

Il tempo di esecuzione di quella particolare coppia di funzioni è infinito perché né ritorna senza chiamare l'altro. Il valore di ritorno di a è sempre dipendente dal valore di ritorno di una chiamata a b che sempre chiama a ... ed è ciò che è noto come < em> infinita ricorsione .

Il metodo ovvio è eseguire la funzione e misurare il tempo necessario. Questo ti dice solo quanto tempo impiega un particolare input, però. E se non sai in anticipo che la funzione termina, dura: non c'è un modo meccanico per capire se la funzione termina - questo è il arresto problema , ed è indecidibile.

Trovare il tempo di esecuzione di una funzione è ugualmente indecidibile, per teorema di Rice . In effetti, il teorema di Rice dimostra che anche decidere se una funzione viene eseguita in O(f(n)) di tempo è indecidibile.

Quindi il meglio che puoi fare in generale è usare la tua intelligenza umana (che, per quanto ne sappiamo, non è vincolata dai limiti delle macchine di Turing) e cercare di riconoscere un modello o inventarne uno. Un modo tipico per analizzare il tempo di esecuzione di una funzione è di trasformare la definizione ricorsiva della funzione in un'equazione ricorsiva sul suo tempo di esecuzione (o un insieme di equazioni per funzioni reciprocamente ricorsive):

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))

E il prossimo? Ora hai un problema di matematica: devi risolvere queste equazioni funzionali. Un approccio che spesso funziona è trasformare queste equazioni in funzioni intere in equazioni su funzioni analitiche e utilizzare il calcolo per risolverle, interpretando le funzioni T_a e T_b come generare funzioni .

Sulla generazione di funzioni e altri argomenti di matematica discreta, consiglio il libro Concrete Mathematics , di Ronald Graham, Donald Knuth e Oren Patashnik.

Come altri hanno sottolineato, l'analisi della ricorsione può diventare molto difficile molto velocemente. Ecco un altro esempio di tale cosa: link link è difficile calcolare una risposta e un tempo di esecuzione per questi. Ciò è dovuto a queste funzioni reciprocamente ricorsive che hanno una "forma difficile".

In ogni caso, diamo un'occhiata a questo semplice esempio:

link

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

Iniziamo cercando di calcolare funa(m), m > 0 :

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

Il tempo di esecuzione è:

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

Ora prendiamo un altro esempio leggermente più complicato:

Ispirato al link , che è di per sé una buona lettura, diamo un'occhiata a: "" "I numeri di Fibonacci possono essere interpretato tramite ricorsione reciproca: F (0) = 1 e G (0) = 1, con F (n + 1) = F (n) + G (n) e G (n + 1) = F (n). " ""

Quindi, qual è il tempo di esecuzione di F? Andremo dall'altra parte.
Bene, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Ora R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
Non è difficile vedere che R (F (m)) = F (m) - ad es. il numero di chiamate di funzione necessarie per calcolare un numero di Fibonacci all'indice i è uguale al valore di un numero di Fibonacci all'indice i. Ciò presuppone che l'aggiunta di due numeri insieme sia molto più veloce di una chiamata di funzione. Se così non fosse, allora sarebbe vero: R (F (1)) = R (F (0)) + 1 + R (G (0)), e l'analisi di ciò sarebbe stata più complicata, possibilmente senza una soluzione di forma chiusa facile.

La forma chiusa per la sequenza di Fibonacci non è necessariamente facile da reinventare, per non parlare di alcuni esempi più complicati.

La prima cosa da fare è mostrare che le funzioni che hai definito terminano e per quali valori esattamente. Nell'esempio che hai definito

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 termina solo per y <= -5 perché se si inserisce un altro valore, si avrà un termine della forma b(a(y-1)) . Se aumenti un po 'di più, vedrai che un termine della forma b(a(y-1)) alla fine porta al termine b(1010) che porta a un termine b(a(1009)) che di nuovo porta al termine b(1010) . Ciò significa che non puoi inserire alcun valore in a che non soddisfi x <= -4 perché se finisci con un ciclo infinito in cui il valore da calcolare dipende dal valore da calcolare. Quindi in sostanza questo esempio ha un tempo di esecuzione costante.

Quindi la risposta semplice è che non esiste un metodo generale per determinare il tempo di esecuzione delle funzioni ricorsive perché non esiste una procedura generale che determina se una funzione definita ricorsivamente termina.

Runtime come in Big-O?

È facile: O (N) - presupponendo che ci sia una condizione di terminazione.

La ricorsione è solo in loop, e un ciclo semplice è O (N) non importa quante cose fai in quel ciclo (e chiamare un altro metodo è solo un altro passo nel ciclo).

Dove sarebbe interessante se hai un ciclo all'interno di uno o più metodi ricorsivi. In tal caso si otterrebbe una sorta di prestazione esponenziale (moltiplicando per O (N) su ogni passaggio attraverso il metodo).