Merci pour la vidéo. Une petite remarque, n'y aurait-il pas une erreur dans l'algo du tri à bulles 1:50? La condition de sortie de la boucle Tantque étant flag=vrai, cette variable ne devrait-elle pas être initialisée à faux (flag=faux), sinon on ne rentre jamais dans la boucle?
Oui. Toute fonction qui domine la complexité dans le pire des cas domine bien sûr la complexité moyenne, et on peut parfois calculer un meilleur majorant asymptotique, ou même calculer une fonction asymptotiquement du même ordre que la complexité en moyenne pour une distribution particulière des données d’entrée, comme par exemple une distribution uniforme. Le problème de la complexité moyenne, c'est qu'elle dépend de la distributions des données d'entrées possibles. Une distribution uniforme, par exemple, n'est pas toujours représentative des données qui seront exploitées en pratique par l'algorithme.
En gros cela revient à calculer somme pour i de 0 à N-3 de somme pour j de 0 à N-2 de n-j-1. On peut voir facilement que cette valeur est inférieure à n^3, donc l'algo est en O(n^3). (Autre manière de la dire : l'algorithme réaliserait n^3 itérations si toutes les boucles allaient de 0 à n-1 et faisaient donc n itérations chacune. Mais comme certaines boucles font clairement moins de n itérations, n^3 est un majorant.) Maintenant, pour montrer que cet algo est aussi en Omega(n^3), il faut trouver un *minorant* du nombre d'exécutions du "if" de la forme K.n^3, ou en tout cas montrer qu'un tel minorant existe. C'est un peu plus technique. Je pense qu'il y a un moyen simple, mais ne le connais pas et je n'ai malheureusement pas le temps de le chercher.
@@ahmedrossoneri Oui, mais la troisième somme est le nombre d'itérations de la troisième boucle, c'est à dire le nombre de valeurs comprises entre j+1 (inclus) et n-1 (inclus), ce qui vaut n-j-1.
Très bonne vidéo. Probablement la plus synthétique et la plus claire sur la complexité d'un algorithme. Merci.
OUI ! Enfin une bonne explication. Tous mes professeurs devraient avoir votre talent pour l'explication. Merci beaucoup pour cette vidéo
Merci pour la vidéo. Une petite remarque, n'y aurait-il pas une erreur dans l'algo du tri à bulles 1:50? La condition de sortie de la boucle Tantque étant flag=vrai, cette variable ne devrait-elle pas être initialisée à faux (flag=faux), sinon on ne rentre jamais dans la boucle?
Tout à fait. Bien vu.
Merci beaucoup à vous, ca m'a totallement permi de mieux comprendre de quoi s'agit la complexité. Merci infiniment
Merci pour cette vidéo Olivier, elle m'a beaucoup servi!
Quelqu’un sait-il où je pourrais trouver des exercices pour m’entraîner sur la complexité algorithmique en temps?
Merci pour la vidéo. Est-il possible d'avoir le même encadrement pour la complexité moyenne ?
Oui. Toute fonction qui domine la complexité dans le pire des cas domine bien sûr la complexité moyenne, et on peut parfois calculer un meilleur majorant asymptotique, ou même calculer une fonction asymptotiquement du même ordre que la complexité en moyenne pour une distribution particulière des données d’entrée, comme par exemple une distribution uniforme. Le problème de la complexité moyenne, c'est qu'elle dépend de la distributions des données d'entrées possibles. Une distribution uniforme, par exemple, n'est pas toujours représentative des données qui seront exploitées en pratique par l'algorithme.
@@OlivierBailleux Merci pour votre réponse !
Pour des boucles comme:
For(int i=0;i
En gros cela revient à calculer somme pour i de 0 à N-3 de somme pour j de 0 à N-2 de n-j-1. On peut voir facilement que cette valeur est inférieure à n^3, donc l'algo est en O(n^3). (Autre manière de la dire : l'algorithme réaliserait n^3 itérations si toutes les boucles allaient de 0 à n-1 et faisaient donc n itérations chacune. Mais comme certaines boucles font clairement moins de n itérations, n^3 est un majorant.)
Maintenant, pour montrer que cet algo est aussi en Omega(n^3), il faut trouver un *minorant* du nombre d'exécutions du "if" de la forme K.n^3, ou en tout cas montrer qu'un tel minorant existe. C'est un peu plus technique. Je pense qu'il y a un moyen simple, mais ne le connais pas et je n'ai malheureusement pas le temps de le chercher.
Je te dis tout les boucles ils terminent par N
Pourquoi tu calcul la somme pour N-3 et N-2 ?
@@ahmedrossoneri Parce que quand i=N-1, la deuxième boucle ne fait aucune itération car la valeur initiale de j est N et le test N
@@OlivierBailleux
Donc pour calculer la classe
Il faut faire 3 sommes n'est pas 2 seulement ou non?
@@ahmedrossoneri Oui, mais la troisième somme est le nombre d'itérations de la troisième boucle, c'est à dire le nombre de valeurs comprises entre j+1 (inclus) et n-1 (inclus), ce qui vaut n-j-1.
un véritable génie
Bravo Bravo
♥♥♥
merci
Génial merci ! Sinon, pas besoin de forcer sur la diction ...
Ouais, j'ai l'impression qu'il me parle comme si j'étais à moitié sourd
Tant que le cours est utile c'est pas un problème