📊

Comparaisons d'algorithmes

Chapitre 7 ‱ Θ/O, OpĂ©rations fondamentales, Comptage & ComplexitĂ©

Statut : En cours
Chapitre 7

Comparaisons d'algorithmes

Comparaison de fonctions (Theta, O), opérations fondamentales, comptage d'opérations (séquences, conditions, boucles, récursivité) et complexité pire/moyenne.

Quel est le titre exact du chapitre 7 ?

#1/20

Que signifie la notation f = Θ(g) pour deux fonctions f et g de N dans R+ ?

#2/20

Quelle est la différence principale entre f = Θ(g) et f = O(g) ?

#3/20

Quelle analogie le cours fait-il entre les notations asymptotiques et les comparaisons de nombres (a, b, c) ?

#4/20

Sur quel type de complexité se concentre principalement ce chapitre ?

#5/20

Qu'appelle-t-on une 'opération fondamentale' pour un problÚme donné ?

#6/20

Quelle est l'opération fondamentale généralement choisie pour la recherche d'un élément dans un tableau ?

#7/20

Quelle est l'opération fondamentale naturelle pour additionner deux matrices ?

#8/20

Comment se comporte le nombre d'opérations dans une séquence d'instructions ?

#9/20

Quelle rÚgle mathématique majore le nombre d'opérations d'un branchement conditionnel (si C alors I sinon I') ?

#10/20

Comment calcule-t-on le nombre d'opérations dans une boucle simple ?

#11/20

Si une boucle s'exécute n fois et effectue à chaque passage 2 additions, quel est le nombre total d'additions ?

#12/20

Combien d'additions effectue l'algorithme d'addition de deux matrices de taille n x m (imbrication de deux boucles de taille n et m) ?

#13/20

Comment traite-t-on les appels de procédure ou de fonction sans récursivité ?

#14/20

Que fait-on en présence de récursivité lors de l'analyse d'une fonction ?

#15/20

Combien de multiplications effectue la fonction factorielle(n) présentée dans le cours ?

#16/20

Pour la fonction récursive f(n) renvoyant n + f(n-2) avec f(0)=f(1)=0, combien d'additions nb(n) effectue-t-on ?

#17/20

Comment est définie la complexité en temps dans le pire des cas Cpire(n) d'un algorithme A pour une opération o ?

#18/20

Comment est définie la complexité en temps en moyenne Cmoy(n) d'un algorithme A ?

#19/20

Que représente concrÚtement la complexité dans le pire des cas pour une taille n ?

#20/20