Discussion :

[bazoga]

Bonsoir,

je cherche un exemple d'algorithme dont la complexité en moyenne est O(1) et dans le cas le pire O(f(n)). // peut importe la fonction f.

aidez moi svp

Cordialement
E.Bazoga

[prgasp77]

Salut, je l'apprends (presque) en même temps que toi : http://fr.wikipedia.org/wiki/Tri_par_paquets

L'idée est pas conne

[Franck Dernoncourt]

Si f est une fonction constante, ça simplifie les choses

[prgasp77]

Mouarf ! détournement de sujet ! Police !

[Franck Dernoncourt]

vite fait, bien fait

[bazoga]

Si f est une fonction constante, ça simplifie les choses

malheureusement, f dépend de n

[Branch]

Salut, je l'apprends (presque) en même temps que toi : http://fr.wikipedia.org/wiki/Tri_par_paquets

L'idée est pas conne

Euh par contre, si je me plante pas, la complexité en moyenne est O(n) et pas O(1)

[prgasp77]

Exact ... quel boulet. Alors j'en ai un, mais il est tordu.

Imaginons un graphe « étoilé » : il y a un nœud A auquel n nœuds Bi sont reliés ; de plus, chaque Bi est relié à b(i-1) et B(i+1) (B1 étant relié à B2 et Bn).

On cherche à aller du nœud B1 au nœud A en suivant cet algorithme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Je marque le nœud courant comme visité
Je choisi un nœud non visité relié au nœud courant
Je m'y rends
Si c'est A, fini, sinon goto 1

En moyenne, il faut 7/3 déplacements et proportionnellement autant d'instructions pour arriver à A, soit un algo de complexité moyenne O(1).
Dans le pire des cas, il faut n+1 déplacements ... algo en O(n) donc.

Cdlt,

[Franck Dernoncourt]

encore plus simple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Dummy(x) // x est un tableau on va dire
A := rand(0, length(x)) // retourne une valeur aléatoire entre 0 (inclus) et length(x)
If A == 0 browse all x's items
return

[prgasp77]

J'ai pas compris ... parcourir tous les éléments de A ... quels éléments ?

[Franck Dernoncourt]

Désolé, je voulais dire parcourir tous éléments de x

[prgasp77]

Dans ce cas, c'est sûrement un '=' à la place du '<', car tel quel, l'ago est en moyenne comme dans le pire des cas en O(n)

[Franck Dernoncourt]

ah oui encore désolé, wow il faut que j'arrête de poster lorsque je me lève !

[bazoga]

Bonjour,

je vous remercie pour l’intérêt que vous portez à mon sujet, en fait j'ai du mal à comprendre comment calculer la complexité en moyenne, si on modifie un peu l'exemple de Mr Franck comme suit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Dummy(t) // t est un tableau on va dire
A := rand(0, length(t)) 
If A == 0 trie_par_tas(t)

est ce qu'on peut dire que cette algorithme a pour complexité en temps moyenne O(1) et en pire des cas O(nlog(n)) "cout du trie" ? si oui, une petite démonstration sera la bienvenue

Cordialement
Bazoga

[Franck Dernoncourt]

Je conseille de lire le chapitre 5 intitulé "Probabilistic Analysis and Randomized Analysis" du livre de référence http://algo.developpez.com/livres/#L2100039229

[pseudocode]

je cherche un exemple d'algorithme dont la complexité en moyenne est O(1) et dans le cas le pire O(f(n)). // peut importe la fonction f.

La plupart des opérations sur une hashtable.

[prgasp77]

Oui, tu devrais plutôt t'intéresser aux exemples donnés par pseudocode ... va savoir pourquoi ça ne nous ait pas passé à l'esprit.

[Franck Dernoncourt]

Ce genre d'énoncé sans grand intérêt, cela donne envie de répondre par un cas tordu, non ?
En outre, l'algo que je donne permet de généraliser facilement pour tout f.

[pseudocode]

Ce genre d'énoncé sans grand intérêt, cela donne envie de répondre par un cas tordu, non ?
En outre, l'algo que je donne permet de généraliser facilement pour tout f.

L'énoncé parle de complexité moyenne (= amortie). Il y a beaucoup de structures de données qui proposent des opérations en complexité amortie constante. Un simple tableau dynamique par exemple.

[Franck Dernoncourt]

Je parle également de complexité moyenne. Une autre façon de tordre les résultats est de poser des hypothèses sur la distribution des entrées données à l'algorithme.

Sinon, si intéressé, un algo de tri O(1) (non utilisable en pratique, et son worst case est également O(1) donc ça ne répond pas à l'énoncé) que j'aime beaucoup : http://www.scribd.com/doc/55808256/2...ting-Algorithm