Est lissée analyse utilisé en dehors du milieu universitaire?

Question

Est-ce que la trouver son chemin dans l'analyse principale de flux d'algorithmes? Est-il courant pour les concepteurs de l'algorithme à appliquer l'analyse lissée à leurs algorithmes?

Answer 1

Je peux me tromper, mais je voir l'analyse lissée comme un moyen de expliquer le comportement en pratique des algorithmes qui ont de mauvaises garanties théoriques (simplex, k-means, et ainsi de suite). Je ne suis pas sûr de ce que cela signifierait pour utiliser analyse lissée en pratique, sauf pour justifier l'utilisation d'une heuristique particulière avec une mauvaise performance du pire ( «Mon heuristique a bla bla comportement pire des cas, mais une analyse lissée indique qu'il fera bien dans la pratique, etc etc ")

Answer 2

La façon dont on analyse des algorithmes dans le monde réel est très différent du monde universitaire. Alors que dans le monde universitaire l'objectif est de trouver un prouvablement correcte limite supérieure sur la durée, dans la vraie vie, l'objectif est de comprendre comment fonctionne l'algorithme, et ce qui peut améliorer tweaks le temps d'exécution. Il existe deux méthodes principales qui sont interdits dans le milieu universitaire, mais utilisés dans la pratique:

• La méthode d'approximation. Ici, vous utilisez beaucoup d'hypothèses simplificatrices pour essayer de prévoir le temps d'exécution d'un algorithme. Semblable à ce que les physiciens théoriques (utilisés pour) faire.
• Expérimentation. Vous exécutez votre algorithme et de mesurer plusieurs statistiques - combien de temps est allé à chaque partie, combien de fois chaque fonction a été appelée, comment était souvent chaque cycle de branche, et ainsi de suite. Ces informations peuvent être utilisées pour optimiser l'algorithme. Expérimentation est également utilisé pour savoir si certaines approximations faites lors de l'analyse du travail de l'algorithme dans la pratique ou non.

Cela dit, je ne pense pas qu'il est très fréquent d'analyser un algorithme dans la pratique, autre que d'ajouter un texte de remplissage dans une publication académique connexe. L'accent est mis soit sur le génie logiciel ou sur l'optimisation de bas niveau, en fonction de la matière.

Enfin, l'analyse lissée est une heuristique qui peut être utilisé pour expliquer pourquoi les algorithmes fonctionnent mieux dans la pratique que leur pire des cas suggère - à savoir puisque certaines des entrées sont « au hasard » dans un certain sens. Cette heuristique peut être utilisé pour rapprocher le comportement de l'algorithme, si l'on utilise la méthode de l'approximation.