Algorithmique - Exemple de résolution d'un problème à l'aide d'un algorithme glouton
HTML-код
- Опубликовано: 19 окт 2024
- Dans cette vidéo, je présente une nouvelle méthode de résolution pour résoudre des problèmes : l'utilisation d'algorithmes gloutons.
Mais auparavant, je reviens rapidement sur les méthodes déjà à votre disposition (force brute et diviser pour régner)
Je présente ensuite cette nouvelle méthode que j'utilise pour résoudre un problème de pokedex.
Elle est à l'attention des étudiants de première année de l'IUT Informatique d'Orléans.
merci
De rien :)
Bonjour, pourquoi le tri d'une liste est en complexité NlogN ? On cherche toujours le plus petit élément d'une liste dont la taille diminue de 1 à chaque fois qu'on trouve le plus petit élément je suppose ? Mais ça ne m'aide pas à voir d'où vient le NlogN...
Merci pour la vidéo au passage :)
L'algorithme que tu décris s'appelle l'algorithme de sélection du minimum. Cet algorithme est en O(N²) et non en O(N log N)
Il existe des algorithmes plus efficaces qui sont en O(N logN). Tu peux aller voir par exemple :
- le tri fusion (merge sort)
- le tri rapide (quick sort)