Entrevue 3.2: comprendre l’efficacité #

NOTE: à faire sur papier (ou avec votre outil préféré pour dessiner des graphes)

Sans regarder la théorie:
- dessiner un graphe pour illustrer la différence entre
  - O(n): linéaire
  - O(n²): quadratique
  - O(2ⁿ): exponentiel
- en X (horizontal): taille des données en entrée, p.ex. de 1 à 10
- en Y (vertical): nombre d’étapes dans le calcul, p.ex. de 1 à 1024
- (note: bien illustrer la tendance est plus important que l’exactitude)

Considérer la version naïve de Fibonacci

public long fib(int n){
    if(n == 0){

        return 0;

    }else if(n == 1){

        return 1;

    }else{

        return fib(n-1) + fib(n-2);
    }
}

Selon vous, quelle est l’efficacité de cette procédure?
Autrement dit, quel est la suite de ce graphique?
Réponse via l'atelier3_2_C!