les_programmes_a_connaitre:algorithmique_premiere:glouton
Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes
Révision précédente
Prochaine révision
|
Révision précédente
|
les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/27 13:43] et |
les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/30 08:28] (Version actuelle) et |
L'algorithme ''Glouton'' est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape sans revenir sur ses décisions. De ce fait, le résultat final n'est pas toujours le plus optimisé. | L'algorithme ''Glouton'' est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape sans revenir sur ses décisions. De ce fait, le résultat final n'est pas toujours le plus optimisé. |
| |
==== L'algorithme Général ==== | Pour sa complexité, si les objets sont déjà triés par ordre décroissant de valeur, alors la boucle bornée de 1 à n correspond à une complexité de l'ordre de O(n). Par contre si la liste des objets n'est pas triée on passe à une compléxité de l'ordre de O(n logn). |
| |
| ==== L'algorithme dans le cas Général ==== |
| |
<code> | <code> |
| |
x : un entier | x : un entier |
f : une liste dans l'ordre croissant | f : une liste ordonnée |
r : une liste | r : une liste |
| |
</code> | </code> |
| |
====Ci-dessous un exemple d'utilisation de celui-ci :==== | ====Ci-dessous un exemple d'utilisation :==== |
| |
=== Problème du voleur === | === Problème du voleur === |
les_programmes_a_connaitre/algorithmique_premiere/glouton.1674823406.txt.gz · Dernière modification: 2023/01/27 13:43 de et