• [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

    Posté par . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 3.

    bof dans la plupart des cas il suffit de reflechir en lisant l'algo. O(1) : facile l'algo ne depend pas du nombre de donnees en entree. c'est rare :-) O(n) : en general l'algo a besoin de parcourir (lire) les donnees en entree au moins une fois. O(n^2) : mauvais. en general l'algo possede deux boucles imbriquées qui dependent du nombre de donnees en entree. En general aussi, on s'arrete la et on note direct O(e^n) pour dire exponentiel (mauvais). en log(n), ton algo ne lit jamais toutes les données, il utilise une astuce (elles sont triées avant d'entrer par exemple, ou dans un hash de mauvaise qualité ...). bon c'est pas academique, mais le feeling ca le fait bien ;-)