Flashcard: Maîtrise des algorithmes gloutons et dichotomie — 14 carte

Complexité algorithme — définition ?

Mesure du nombre d'opérations en fonction de n.

Notation O — rôle ?

Classe et compare la croissance asymptotique.

Complexité constante O(1) — description ?

Opérations fixes, indépendantes de n.

Complexité linéaire O(n) — description ?

Proportionnelle à la taille n.

Complexité logarithmique O(ln(n)) — description ?

Croît en fonction du log de n.

Complexité quadratique O(n²) — description ?

Proportionnelle au carré de n.

Algorithme glouton — principe ?

Choix local optimal espérant solution globale optimale.

Solution optimale dans glouton — condition ?

Propriété spécifique du problème ou système.

Rendu de monnaie — objectif ?

Minimiser le nombre total de pièces utilisées.

Système monétaire canonique — définition ?

Algorithme glouton toujours optimal.

Algorithme glouton — exemple ?

Rendu de monnaie dans système canonique.

Planning d’occupation — but ?

Maximiser conférences sans chevauchement.

Critère glouton planning — choix ?

Intervalle qui se termine le plus tôt.

Recherche dichotomique — principe ?

Diviser l’intervalle en deux pour localiser une racine.