Dare una stretta analisi di run-time-oh grande per questo frammento di codice

Question

public static long F (int N) { 
    if (N == 1) return 1; 

    return F(N - F(N-1)); 
} 

Ora ho pensato che l'interno F (N-1) verrà eseguito N volte per ciascuna delle F (N - F (N-1)) e così sarà N ma quella non sembra essere la risposta.

Qualcuno può dirmi perché?

Answer 1

Per calcolare questo fuori, immaginiamo riscrivere il codice in modo equivalente:

public static int F (int N) { 
    if (N == 1) return 1; 
    int k = F(N - 1); 
    return F(N - k); 
} 

Tutto quello che ho fatto qui è tirare fuori la chiamata interiore per F(N - 1) e spostarlo verso l'alto-livello in modo che possiamo vedere più chiaramente che questo codice effettua due chiamate a F e che la seconda chiamata è relativa a un sottoproblema che dipende dalla prima chiamata.

Per determinare il runtime qui, avremo bisogno di capire che cosa è k in modo che possiamo vedere che tipo di chiamata ricorsiva stiamo facendo. Interessante, si scopre che F (N) = 1 per tutte le N. È possibile individuare questo schema qui:

• F (1) = 1.
• F (2) = F (2 - F (1)) = F (2 - 1) = F (1) = 1
• F (3) = F (3 - F (2)) = F (3 - 1) = F (2) = 1
• F (4) = F (4 - F (3)) = F (4 - 1) = F (3) = 1

E 'un ottimo esercizio per dimostrare questo per induzione.

Questo significa che la chiamata a F (N - k) chiamerà F (N - 1). Ciò significa che il codice è funzionalmente equivalente a

public static int F (int N) { 
    if (N == 1) return 1; 
    int k = F(N - 1); 
    return F(N - 1); 
} 

Questo ha relazione ricorrente

• F (1) = 1
• F (n) = 2F (n-1) + 1

Quale soluzione F (n) = 2 ⁿ - 1. (Anche in questo caso, è possibile provarlo formalmente per induzione, se lo si desidera). Pertanto, la complessità è Θ (2 ⁿ).

Per convalidare questo, ecco una (davvero hacky) lo script C che chiama la funzione su un certo numero di ingressi differenti, riportando il valore restituito e il numero delle chiamate effettuate:

#include <stdio.h> 

/* Slightly modified version of F that tracks the number of calls made   
* using the second out parameter.            
*/ 
static int F (int N, int* numCalls) { 
    /* Track the number of calls. */ 
    (*numCalls)++; 

    if (N == 1) return 1; 
    return F (N - F (N-1, numCalls), numCalls); 
} 

int main() { 
    for (int i = 1; i < 10; i++) { 
    int numCalls = 0; 
    int result = F(i, &numCalls); 
    printf("F(%d) = %d, making %d calls.\n", i, result, numCalls); 
    } 
} 

L'uscita è

F(1) = 1, making 1 calls. 
F(2) = 1, making 3 calls. 
F(3) = 1, making 7 calls. 
F(4) = 1, making 15 calls. 
F(5) = 1, making 31 calls. 
F(6) = 1, making 63 calls. 
F(7) = 1, making 127 calls. 
F(8) = 1, making 255 calls. 
F(9) = 1, making 511 calls. 

si noti che la valutazione (i) F prende sempre 2 ⁱ - 1 chiamate (proprio come la teoria previsto!) e restituisce sempre 1, empiricamente convalidando l'analisi matematica.