Complexité algorithmique

[ampholyte]

Bonjour,

Une petite question me vient en tête lorsque l'on souhaite calculer la complexité d'un algorithme.
N'ayant jamais eu de cours, je me suis renseigné de mon côté mais quelques complexités me laissent perplexes.

Prenons en exemple la dichotomie :

Code: Tout sélectionner

int debut = 0;
int fin = 1000;
int milieu = 0;
bool trouve = false;
int tab[1001] = {0};
int parametre = 100

/* Initialisation du tableau */

do {
    milieu = (debut + fin)/ 2;

    if (tab[milieu] == parametre) {
        trouve = true;
    } else if (tab[milieu] > parametre) {
        fin = milieu - 1;
    } else {
        debut = milieu + 1;
    }
} while (!trouve && debut <= fin)


Après quelques recherches j'ai trouvé que la dichotomie avait une complexité en log(N). Comment peux-t'on retrouver se résultat ?

Merci d'avance.

[Archytas]

Salut,
Je me souviens pas très bien mais pars d'un tableau ayant 2^n cases et comte le nombre maximal d'opération effectué (d'ailleurs le résultat est en log_2(n) et non log(n)) !
Voilà !

[ampholyte]

Oui j'essaye d'appliquer la même méthode que pour le calcul sur d'autres algos mais je ne comprends pas comment est-ce qu'on peut retomber sur log_2(N) (merci pour l'info, j'ai lu log(n) sur un autre site) à partir d'un comptage en fonction de N.

[fatal_error]

archytas te propose de compter avec 2^N cases.
Dans le pire des cas:
tu divises par 2, 2^(N-1) cases et t'as pas la solution
tu redivises par 2, 2^(N-2) cases et t'as pas la solution
...
2, tu redivises par 2 et t'as plus qu'une ase, tu trouves la solution.

Tu as donc appliqué la division/essai N fois.
tu fais le changement de variables N=log_2(n)

et il vient pour 2^N=2^log_2(n)=n cases, tu appliques l'iteration log_2(n) fois.
idem ton algo est en log_2(n)

[ampholyte]

D'accord merci beaucoup !

Je n'avais pas penser au changer de variable, du coup je comprends mieux =).

Merci encore .

[LeJeu]

Oui j'essaye d'appliquer la même méthode que pour le calcul sur d'autres algos mais je ne comprends pas comment est-ce qu'on peut retomber sur log_2(N) (merci pour l'info, j'ai lu log(n) sur un autre site) à partir d'un comptage en fonction de N.

il n'y a pas de distinction à faire entre log_2 et log à propos de complexité d'algorithme

quand on dit qu'un algo est de complexite O( log(n))
cela veut dire que le nombre d'opérations est < C log(n)
ou C est une constante
entre Log_2 et log , il n'y a qu'une différence de constante

( fatal_error et ampholyte te donne la constante)

[ampholyte]

Merci pour cette précision, c'est noté =).

[Rockleader]

Au risque de poser une question idiote, qu'est ce que tu entend par complexité ?

(Simple curiosité de ma part).

Votre discussion me rappelle un peu ce que j'avais sur le coût d'un algorithme.

[ampholyte]

La complexité est ce qui permet de caractériser un algorithme afin de savoir si celui-ci est performant ou non.

Par exemple, un algorithme de complexité N² sera moins performant qu'un algorithme de complexité N.

Pour plus d'info
http://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes#D.C3.A9finition

[Archytas]

Salut, la complexité algorithimique est une invention (ou découverte selon les points de vue) de Chaitin.

Complexité algorithmique : La complexité algorithmique d'une sortie informatique est la taille du plus petit programme autodélimité donnant cette sortie. La complexité est comparée à la taille de la sortie. Si la complexité d'une sortie est au moins de l'ordre de sa taille, alors la sortie sera dite algorithmiquement aléatoire.

:++:

[Rockleader]

Ok, merci pour vos réponses, j'irai voir ça à l'occasion.

[ampholyte]

Petite indication, j'ai trouvé une méthode plus simple pour répondre à ma question principale.

Il vaut mieux écrire en base 2 directement N. La division par 2 provoquant un décalage vers la droite.

Combien de fois peut-on diviser N par 2, autant de fois qu'il y a de bit donc log(N).

Merci encore !