Complexité amortie, optimalité et stratégie

Bonjour,

J’ai commencé à écrire un article sur la complexité amortie. Je voulais présenter les résultats classico-classiques. Je dois encore relire et améliorer les endroits où c’est peu compréhensible. C’est le premier jet.

Merci !

Hello,

Juste au cas où, définis bien ta cible (au cas où parce que je ne peux pas juger de si tu en respectes bien une) Je crois bien que tu vises des personnes ayant déjà des connaissances dans le domaine, dans ce cas tu peux le préciser en intro, éventuellement.

Voilà, je suis un peu repassé partout pour corriger des problèmes de présentation et de sens. La fin me paraît fort abrupte mais je compte réserver un autre article au cas des splay-tree spécifiquement (+tango tree).

Je suis prêt à recevoir vos retours.

Salut,

L’article est intéressant à lire mais je trouve les transitions d’une section à une autre parfois difficiles. Peut-être pourrais-tu revenir de temps en temps sur les exemples pour illustrer l’application de telle ou telle méthode sur le problème initial ?

Bonjour,

Je ne sais pas trop comment interpréter ta demande Entwanne. Il y avait clairement un manque de transitions (que dire, une falaise) entre la fin de l’analyse du disjoint-set et les notions de c-competitive. Néanmoins, je suis repassé sur plusieurs parties pour corriger des fautes et modifier les liaisons. Maintenant que cela fait un petit temps que j’ai écrit cela, je me rends compte à quel point le "disjoint-set" est compliqué

En lisant je trouvais qu’après avoir illustré un concept avec un problème algorithmique, tu partais dans les calculs liés à la complexité mais sans appliquer ensuite ces résultats au problème de départ.