La complexité des algorithmes,Par Mme Imen KHOUJA,Numérique et Sciences informatiques - Classe de premièreAvril 2020,Index,Rappel sur les méthodes de recherches,De quoi dÉpend la complexitÉ ?,Rappel sur les méthodes de Tri,Comparaison des méthodes de tri,CALCUL SUR PYTHON,Définition,Classe de complexitÉ,Introduction,Calcul de complexitÉ,ActivitÉ 2,Fonction time,ActivitÉ 1,application,fin de la sÉquence,A retenir,quiz,Problème,Solution 1Solution 2...Solution n,Traitement,3,Implémentation,Ecriture de l'algorithme,1,Test,4,Exécution à la main,2,VS,Tri Sélection,Tri Insertion,Plus d'infos,PLUS D'INFOS,Recherche dichotomique,Recherche séquentielle,Simulation des différentes méthodes de tri,Cas 1,Cas 2,Cas 3,Cas 4,1- Définition de la complexité,Complexité temporelle,Complexité Spatiale,La complexité (temporelle) d’un algorithme est le temps nécessaire à résoudre un problème mathématique P, En informatique théorique, ce temps est mesurée par le nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques) effectuées par un algorithme. ,Renvoyercourant en secondes,2- Calcul du temps d’exécution avec Python,time(),Combien de temps la fonction a-t-elle mis à s’exécuter ? ,Info,Activité 1,Correction,Sur votre TP python, calculez le temps d’exécution de chaque fonction de tri étudiée en utilisant la fonction time().Effectuez le test pour une liste de taille : 5, 20, 100 et 1000,Info,Correction de l'activité 1,20,1000,32.68,5,Résultats en secondes(x 100 000),3.45,100,5.14,34.52,3115.84,3702.52,4.0,Lorem Ipsum,Lorem Ipsum,Tri Sélection,4.50,Lorem Ipsum,Lorem Ipsum,Tri Insertion,Calculez le temps d’exécution des fonctions recherche séquentielle et dichotomique en utilisant la fonction time() pour une liste de taille 10 puis 100 en testant les scénarios suivants :- L'élément à rechercher se trouve au début de la liste.- L'élément à rechercher se trouve au milieu de la liste.- L'élément à rechercher ne se trouve pas dans la liste.,Correction,Activité 2,CAs 1,?,?,Correction de l'activité 2,?,Résultats en secondes (x 100 000),Lorem Ipsum,Cas 2,Cas 3,Lorem Ipsum,Séquentielletaille = 10,?,Dichotomiquetaille = 10,?,3115.84,Lorem Ipsum,Lorem Ipsum,Séquentielletaille = 100,Dichotomiquetaille = 100,?,?,?,?,?,?,?,3- De quoi dépend la complexité ?,La notation O = Ordre de grandeur asymptotique,Complexité,Conditions de départ,Taille des donnéesN,Meilleur cas,Cas moyen,Pire cas,Si T est le nombre d'opérations élémentaires.T= N ou T= 3N+5 ou T=N/2La complexité est en O(N),Info,4- Classes de complexité des algorithmes,Complexité logarithmiqueComplexité linéaireComplexité quadratiqueComplexité polynomialeComplexité exponentielle Complexité hyperexponentielle,Info,5- Calcul de la complexité,Info,Algorithmes sans structures conditionelles,Algorithmes avec structures conditionelles,Info,Algorithmes avec structures itératives,Info,Algorithmes sans structures conditionnellese,Example : Une fonction de conversion,3 affectations,5 opérations arithmétiques,T(n) = 8,O(1),Complexité constante,1 opération arithmétique +1 comparaison,Algorithmes avec structures conditionnelles,+1 affectation pour chaque alternative,Example : Un calcul de puissance,T(n) = 3,O(1),T(n) = 5N +1,Example : Calcul de la somme desnpremiers entiers,Algorithmes avec structures itératives,1 affectation,O(N),1 affectation, 1 addition, 1 comparaison,1 affectation, 1 addition,5 opérations élémentaires x N fois = 5N,Complexité linéaire ,A retenir : Plan d’étude de la complexité d’un algorithme,Il faut définir l’entier n représentant la taille des arguments.,1,On prendra par exemple :- n = n si l’argument est un entier n- n = la longueur de L si l’argument est un tableau de longueur n,2,Il faut définir l’unité de coˆut.,On prendra par exemple :- le nombre de multiplications si la multiplication est l’opération dominante- le nombre d’itérations si le nombre d’opérations et de tests sont constants par itération- le nombre de comparaisons si aucune autre opération importante n’est effectuée,Calculez la complexité de chacune de ces fonctions.,6- Applications,Solution,Solution,START,QUIZ,Déterminez la complexité de chaque fonction proposée.,C,O(n),O(n2),A,O(1),B,2,1,3,fonction 1,O ( n2 ) (n au carré),O ( 1 ),1,O ( n ),B,A,C,2,3,fonction 2,B,C,3,O ( n2 ) (n au carré),O ( 1 ),A,2,O ( n ),1,fonction 3,4,1,merci !,2,3