Algorithmes efficaces et recherche médiane

Cette séance de cours couvre différents algorithmes, y compris le calcul du carré d'un grand entier plus efficacement que le produit de deux grands entiers, un ancien algorithme récursif égyptien pour la multiplication entière, et un algorithme de recherche médiane. Il examine également l'efficacité de ces algorithmes par rapport à la multiplication de Karatsuba et leur complexité temporelle. L'instructeur présente des exercices sur ces sujets, comme tester la justesse de l'algorithme, le lien avec la décomposition binaire et l'analyse de la complexité temporelle. De plus, un algorithme de recherche médiane en place est proposé, comportant la subdivision d'une liste en trois sous-listes. La séance de cours se termine par des algorithmes de tri non conventionnels et leur analyse de complexité temporelle.