Bonjour à vous tous.  
 
Je suis en train d'étudier les Calendar Queues, une structure de listes avec des Buckets. Cependant quand j'étudies la complexité, je tombe sur une complexité de l'ordre de O(n*n). Cependant dans l'article ils parlent bien d'une complexité de O(1). Quelqu'un peut m'expliquer comment ils arrivent à trouver ce résultat?
 
Merci beaucoup !!
 
Article:  
http://pi4.informatik.uni-mannheim [...] n1988a.pdf
 
 

Bon bah à priori faire un up est interdit ici....

Désolé d'être habitué à la section hardware ou ça défile toutes les heures ^^

Tu utilises quoi comme structure de données pour tes buckets ?
Tu calcules la complexité d’insertion ou de suppression ?
 
A l'insertion, le temps est constant au regard du nombre et de la taille des buckets.
Pour la suppression, l'explication dépend de ta structure de données.

Pour les buckets, en fait c'est un vecteur, et chaque variable de ce vecteur pointe vers une valeur dans une liste.  
 
La complexité que je calcule c'est la recherche d'un élément dans les listes.  
 
Cependant si j'ai bien compris dans l'article ils utilisent des files au lieu des listes, ce qui fait qu'ils insèrent toujours à la queue, et ils suppriment toujours la tête. C'est ça qui rend peut être la complexité constante...
 
Dans mon cas je vais pouvoir insérer à chaque endroit.

Le choix d'implémentation de bucket est à ta charge, et dépend donc de tes contraintes / critères de recherche.
 
J'ai pas lu l'article, mais de mémoire l'utilisation d'une queue (ton exemple) n'a rien d'obligatoire, tu pourrais tout aussi bien maintenir un index spécifique.
 

Ah d'accord, donc j'imagine que la complexité de O(1) vient de là, ils ont pris la structure la plus facile Je te remercie pour tes conseils et ça m'aide beaucoup pour la mise en place de cette structure