Complexité, Tris ...
Quelques exercices sur la récursivité et la stratégie diviser pour régner en utilisant la technique de dénombrement
Exercices corrigés sur la récursivité (Niveau avancé)
Nous voulons souvent raisonner sur le temps d'exécution d'une manière qui ne dépend que de l'algorithme et de son entrée. Ceci peut être réalisé en choisissant une opération élémentaire, que l'algorithme effectue à plusieurs reprises, et en définissant la complexité temporelle \(T(n)\) comme le nombre de ces opérations que l'algorithme effectue étant donné un jeu de données de longueur n.
Un invariant doit satisfaire trois propriétés : initialisation, maintenance et terminaison. Ces trois étapes constituent une preuve par induction que l'algorithme produit le résultat attendu.
Le tri par fusion est l'un des algorithmes de tri les plus populaires et les plus efficaces. Et il est basé sur le paradigme Diviser pour régner.
Un algorithme de tri est utilisé pour réorganiser les éléments d'un tableau ou d'une liste donnée selon un ordre (croissant, décroissant) en utilisant l'un des opérateurs de comparaison ().
pour la boucle for le coût est proportionnel au nombre d'itérations, par contre pour une une boucle while, il faut estimer le nombre d'itérations.
Le problème consiste de compter tous les chemins possibles dans une grille MxN avec des contraintes ,,,
La programmation dynamique est une technique efficace pour résoudre des problèmes d'optimisation. Il est basé sur la décomposition du problème initial en problèmes plus simples et la résolution de ces sous-problèmes à partir des plus simples.
La recherche dichotomique (ou recherche binaire) est un algorithme de recherche qui permet de trouver la position d'une valeur cible dans un tableau trié.
Dans l'approche diviser pour régner, le problème en question est divisé en sous-problèmes plus petits, puis chaque problème est résolu indépendamment. Si nous continuons à diviser les sous-problèmes en sous-problèmes encore plus petits, nous pouvons éventuellement atteindre un stade où plus aucune division n'est possible.
Étant donné la longueur du mur L et des étagères de deux longueurs m et n, trouvez le nombre de chaque type d'étagère à utiliser et l'espace disponible restant dans la solution optimale, de sorte que l'espace vide soit minimal.