|
Bas de page | |
---|---|
Auteur | Sujet : [Résolu] Evaluer la complexité de morceaux d'algo |
![]() Publicité | Posté le 27-12-2006 à 21:27:43 ![]() ![]() |
pains-aux-raisins Fatal error | pour la 2ème complexité, on peut améliorer l'estimation à O(ln(ln(n))). Message édité par pains-aux-raisins le 28-12-2006 à 14:03:35 |
pains-aux-raisins Fatal error | la 3ème complexité est bien O(n) Message édité par pains-aux-raisins le 28-12-2006 à 14:03:18 |
pains-aux-raisins Fatal error | pour la 1ere complexité, en déroulant l'aglorithme, on sent que O(n) n'est pas la bonne réponse. Ca serait plutôt O(n.ln(n)) |
Pwill Deux fois Né | Je te remercie de ton aide |
pains-aux-raisins Fatal error | pour la 2ème complexité, il faut partir de l'inégalité j<k dans la boucle tantque.
|
Pwill Deux fois Né |
Message cité 1 fois Message édité par Pwill le 28-12-2006 à 18:28:44 |
pains-aux-raisins Fatal error | non, tout simplement O(log2(n)) Message édité par pains-aux-raisins le 28-12-2006 à 19:14:01 |
Shynia | Bonjour,
|
pains-aux-raisins Fatal error | Euh, l'instinct pour calculer les complexité ???
|
![]() Publicité | Posté le 03-01-2007 à 17:15:43 ![]() ![]() |
Shynia |
Pour cet algo, je trouve : nlog(n) Message édité par Shynia le 03-01-2007 à 17:25:58 |
pains-aux-raisins Fatal error | hmmm, imagine que tu a à la ligne 2, j:=n au lieu de j:=i.
|
Shynia | C'est n'est pas plutot log2(n) dans le Tant Que, etant donné qu'on ne fais pas ca pour toutes les valeurs de n à 1 ??
|
pains-aux-raisins Fatal error | En regardant mon calcul, j'ai fait une erreur.
|
Shynia | Merci beaucoup ^^
|
pains-aux-raisins Fatal error | Non, car ici j n'est initialisé qu'au début, à l'extérieur de la boucle pour.
|
Shynia | Raahh minceeeee
|
pains-aux-raisins Fatal error | Imaginons, n=100 Le maximum de i*(n-i) est atteint pour i=n/2 qui provoque également la fin de l'algorithme. j a une progression linéaire et est même égal à i*(n-i) quand l'algo s'arrête. On a donc une complexité de O(n/2) soit O(n). Message cité 1 fois Message édité par pains-aux-raisins le 03-01-2007 à 21:36:19 |
Pwill Deux fois Né | Zut, en fait je me plante sur les exemples de Shynia... et l'exam c'est demain aprem... |
pains-aux-raisins Fatal error |
Pwill Deux fois Né |
Message édité par Pwill le 04-01-2007 à 00:35:40 |
Pwill Deux fois Né |
Message édité par Pwill le 03-01-2007 à 23:34:45 |
Pwill Deux fois Né | J'ai repris l'avant dernier message où j'avais écrit des bétises. J'ai corrigé mais il reste un point à éclaircir dans ma tête...
|
angelx24 | Ahh c'est beau les études d'info, enfin c'est mieux lorsque l'on a finit.
|
rufo Pas me confondre avec Lycos! | je serais curieux de savoir le nb d'ingé en infos qui, une fois dans la vie active, calculent encore la complexité de leurs algos... |
angelx24 | On est pas nombreux effectivement, mais l'expérience prime sur le calcul.
|
rufo Pas me confondre avec Lycos! | certes, mais ça viendrait à l'idée d'aucun ingé d'utiliser le buble sort pour trier. De suite, il va partir sur le quick sort (même si c'est pas le plus performant) ; en +, on le trouve implémenté de base dans la plupart des langages de dév. |
pains-aux-raisins Fatal error | bah, le calcul de la complexité a au moins le mérite de sensibiliser au problème. Et vu le nombre d'appli mal codée, je trouve même qu'une petite révision pour bcp d'ingé ne leur ferait pas de mal |
angelx24 | Le quick sort est utilisé par tout le monde même si une dicho pour le fun de temps en temps, ça fait pas de mal hehe !!
|
pains-aux-raisins Fatal error | Merci pour la leçon angelx24, mais disons que je ne suis plus à l'école depuis longtemps |
angelx24 | Et bien alors, tu sais que les programmeur sont fainéants de nature et que le temps manque pour la grande majorité des projets, cahiers des charges etc... donc tu connais la musique du cycle en V. |
Pwill Deux fois Né | Si vous avez quelques minutes, vous pensez quoi de ces boucles:
Message édité par Pwill le 04-01-2007 à 19:41:02 |
pains-aux-raisins Fatal error | Pb à la ligne 2 : pas de borne max dans la boucle pour |
Pwill Deux fois Né | Désolé, 2 erreurs en recopiant le sujet |
0x90 → |
--------------- Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck. |
deadalnix | clair, tu passe d'un log a l'autre par simple multiplication.
|
![]() Publicité | Posté le ![]() ![]() |
Sujets relatifs | |
---|---|
[resolu]formulaire avec modification texte(couleur ,...) | [Résolu] Bien sur IE, probleme sur Firefox |
[Resolu] Comment lire dans un fichier ligne par ligne | [Résolu] Javascript / AJAX - Problème de réponse de requete |
[Résolu] Comment utiliser le JRE 1.5 sous Eclipse ? | [C++] évaluer l'espace mémoire occupée par une application |
[RESOLU] probleme d'égalités CA URGE MERCI LES GENS | [ Résolu] [Cobol] chaîne vers numérique |
[Résolu][C#] Générer un PDF avec des images Dynamiques (ASP.Net 1.1) | [Résolu] Problème de header session_start() |
Plus de sujets relatifs à : [Résolu] Evaluer la complexité de morceaux d'algo |