Comment déterminer le Big O d'un algorithme récursif qui inclut une optimisation?

Question

Je sais que la fonction récursive régulière pour l'algorithme fibonacci est O (2^n) car elle s'appelle deux fois pour chaque appel suivant, doublant son coût. Cependant, après avoir ajouté ce que j'ai vu décrit comme une optimisation (une hashtable de solutions à la séquence), comment déterminez-vous combien cela réduit la complexité, voire pas du tout?

Par exemple:

import java.util.*; 

public class Solution { 

    static Hashtable<Integer, Integer> numbers = new Hashtable<Integer, Integer>(); 

    public static int fibonacci(int n) { 
     if(n == 0 || n == 1){ 
      return n; 
     }else if(numbers.containsKey(n)){ 
      return numbers.get(n); 
     }else { 
      int result = fibonacci(n-1) + fibonacci(n-2); 
      numbers.put(n, result); 
      return result; 
     } 
    } 

    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     int n = scanner.nextInt(); 
     scanner.close(); 
     System.out.println(fibonacci(n)); 
    } 
} 

Answer 1

Votre algorithme est O (n). Ce que vous avez implémenté est ce qu'on appelle la mémoisation. Ce que cela signifie réellement, c'est que lors de la rupture du problème dans deux sous-problèmes (ou plus généraux) qui se chevauchent partiellement (eg F(5) = F(4) + F(3)), les deux devront calculer F (2) pour qu'ils se chevauchent) quand une valeur est calculée, elle est stockée. le temps nécessaire sera déjà calculé.

Cela signifie que pour calculer F(n) vous récursive calculer tous F(i) ,i<n et si certains F(i) est plus d'une fois nécessaire, il sera calculé qu'une seule fois et sera disponible en O(1) (due o Hashtable) .Donc sont ci O(n). Ceci est très similaire à la version de l'algorithme dynamique (avec la petite différence que, au lieu de construire les solutions par exemple F (0), F (1), F (2) ... F (n), vous le faites à rebours garder une trace de ce que vous avez calculé (mémoization)). Bien que je n'ai pas vérifié si votre algorithme de mémoisation a un bug ... il suffit d'expliquer le concept et la complexité de l'algorithme de mémoisation.

Answer 2

Comme indiqué dans les commentaires, la complexité de cette fonction est Theta (2^n):

Fibonacci(n) { 
    if (n < 0) return 0; 
    if (n < 2) return 1; 
    return Fibonacci(n - 1) + Fibonacci(n - 2); 
} 

Nous pouvons prouver par induction. Cas de base: pour n = 0 et n = 1, 0.5 * 2^n <= Fibonacci(n) = 1 <= 2 * 2^n. Hypothèse d'induction: supposons que cela vaut pour n jusqu'à et y compris k. Étape d'induction: montrez que 0.5 * 2^(k+1) <= Fibonacci(k+1) <= 2 * 2^(k+1). En remplaçant, nous obtenons 0.5 * 2^(k+1) = 2*2^(k-1) <= 2*Fibonacci(k-1) <= Fibonacci(k) + Fibonacci(k-1) <= 2*Fibonacci(k) <= 2 * 2^k <= 2 * 2^(k+1). Ceci complète la preuve.

Hashtable des solutions (parfois appelé une note de service , d'où memoization) empêche Fibonacci(k) d'être invoqué plus d'une fois par k. Puisque dépend seulement de Fibonacci(0), Fibonacci(1), ..., Fibonacci(n-1), et puisque la hashtable et la vérification empêchent n'importe lequel de ceux-ci d'être appelés plus qu'une fois, chacun est appelé exactement une fois, et puisque chacun fait une quantité constante de travail pour n'importe quel donné n, la quantité totale de travail est O(n). La relation de récurrence est plus difficile à penser maintenant (nous avons des effets secondaires et des conditions conditionnelles) donc je dois me prévaloir de ce genre d'argument "trick". Malheureusement, la plupart des preuves nécessitent une sorte de "truc", l'induction étant une sorte d'exception.