En informatique, l'analyse amortie est une méthode d'évaluation de la complexité temporelle des opérations sur une structure de données. Cette analyse résulte en une classification des algorithmes et conduit à une théorie spécifique de la complexité des algorithmes que l'on appelle complexité amortie.
L'analyse amortie consiste essentiellement à majorer le coût cumulé d'une suite d'opérations pour attribuer à chaque opération la moyenne de cette majoration, en prenant en compte le fait que les cas chers surviennent rarement et isolément et compensent les cas bon marché. Pour être utilisable, cette analyse suppose que l'on est capable de borner la fréquence des cas les plus coûteux. L'analyse amortie se place dans le cas le plus défavorable et garantit la performance moyenne de chaque opération dans ce cas. À partir de l'analyse amortie on peut concevoir des structures de données efficaces.
L'analyse amortie étudie la complexité (temporelle) d'une suite d'opérations effectuées sur une même structure de données. Elle répartit le surcoût de certaines opérations dispendieuses sur toutes les opérations en prenant en compte le fait que la plupart des opérations sont économes. Elle attribue à chaque opération d'une séquence un coût amorti qui est la moyenne arithmétique du coût total sur l'ensemble de ces opérations. Compte tenu des compensations entre opérations (les opérations bon marché en temps contrebalançant les opérations coûteuses), ce temps est, en général, nettement meilleur que celui que donnerait une analyse dans le pire cas.
En répartissant les coûts élevés de certaines opérations sur toutes les opérations, elle escompte qu'un coût moyen raisonnable sera associé à chaque opération. La répartition du coût sur une séquence d'opération ressemble à un amortissement en comptabilité. Le résultat de cette analyse est une majoration de la performance moyenne de chaque opération.
Cette analyse est utilisée avec profit quand on étudie une structure de données qui implique des coûts importants lors d'opérations peu fréquentes comme des rééquilibrages ou des améliorations de son état interne.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. Usually the resource being considered is running time, i.e. time complexity, but could also be memory or some other resource. Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n.
Explore la mise en œuvre et l'efficacité des piles et des files d'attente, ainsi qu'un défi algorithmique impliquant la détermination des ordres de train.
A shift from fossil-based energy and products to more sustainable alternatives is essential to reduce greenhouse gas emissions and associated climate change impacts. Biomass represents a promising alternative for providing fuels and carbon-based products w ...
EPFL2023
,
Total Flow Analysis (TFA) is a method for the worst-case analysis of time-sensitive networks. It uses service curve characterizations of the network nodes and arrival curves of flows at their sources; for tractability, the latter are often taken to be line ...
In this thesis we design online combinatorial optimization algorithms for beyond worst-case analysis settings.In the first part, we discuss the online matching problem and prove that, in the edge arrival model, no online algorithm can achieve a competitive ...