Complexité en temps | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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. La complexité en temps étant la mesure la plus courante en algorithmique, on parle parfois simplement de la complexité d'un algorithme, mais il existe d'autres mesures comme la complexité en espace. Calculer les complexités d'un algorithme, et en particulier la complexité en temps est parfois complexe, et cette étude constitue en elle-même une discipline : l'analyse de la complexité des algorithmes. La complexité en temps compte le nombre d'étapes de calcul. Il y a plusieurs façons de définir ces étapes, par exemple le nombre d'opérations dans une machine RAM, ou des mesures plus théoriques comme le nombre de comparaisons dans le cas d'un algorithme de tri ou le nombre de pas d'une machine de Turing. L'étude du temps de calcul consiste souvent à donner une borne supérieure sur le nombre d'étapes, exprimée par un ordre de grandeur. Par exemple dans le cas de l'algorithme tri fusion, on parle d'une complexité en , ce qui signifie qu'il existe une constante telle que pour toute entrée de taille le nombre d'étapes sera inférieur à . Le temps, comme défini plus haut, est lié au temps de calcul réel mais c'est une mesure plus abstraite, qui dépend de l'algorithme et de l'entrée mais est indépendante de la puissance de l'ordinateur par exemple (on compte des étapes de calcul et non des secondes).

À propos de ce résultat

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.

Publications associées (109)

Personnes associées (52)

Unités associées (1)

Concepts associés (165)

Cours associés (97)

Séances de cours associées (537)

MOOCs associés (8)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

CS-251: Theory of computation

This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica

CS-250: Algorithms

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

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have

IEEE COMPUTER SOC2022

The Universal Gossip Fighter

Rachid Guerraoui, Anne-Marie Kermarrec, Rafaël Benjamin Pinot, Anastasiia Kucherenko

The notion of adversary is a staple of distributed computing. An adversary typically models “hostile” assumptions about the underlying distributed environment, e.g., a network that can drop messages,

2022

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a sin

EPFL2022

vignette La formule de Stirling, du nom du mathématicien écossais James Stirling, donne un équivalent de la factorielle d'un entier naturel n quand n tend vers l'infini : que l'on trouve souvent écrite ainsi : où le nombre e désigne la base de l'exponentielle. C'est Abraham de Moivre qui a initialement démontré la formule suivante : où C est une constante réelle (non nulle). L'apport de Stirling fut d'attribuer la valeur C = à la constante et de donner un développement de ln(n!) à tout ordre.

thumb|Comparaison entre une croissance linéaire (en rouge), cubique (en bleu) et exponentielle (en vert) |300x300px La croissance exponentielle d'une quantité est son augmentation au fil du temps selon une loi exponentielle. On l'observe quand la dérivée par rapport au temps de cette quantité (c'est-à-dire son taux de variation instantané) est positive et proportionnelle à la quantité elle-même. Dans la langue courante on emploie souvent, mais improprement, le terme « croissance exponentielle » pour qualifier une augmentation simplement accélérée, quand la dérivée est elle-même croissante.

En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard. Ce genre de machine permet de définir des classes de complexité intéressantes et de donner un modèle de calcul pour les algorithmes probabilistes comme le test de primalité de Miller-Rabin. Il existe différentes définitions équivalentes des machines de Turing probabilistes. Dans la suite tous les tirages sont indépendants et uniformes.

Algorithmes : Analyse de l'efficacité

Couvre l'analyse de l'efficacité de l'algorithme et l'optimisation du code pour une exécution plus rapide.

Slide design pour vidéos éducatives

Couvre la conception de diapositives pour des vidéos éducatives et discute de la complexité du temps, des bases de diffraction et des systèmes de contrôle Shuttle.

Complexité des algorithmes : la complexité des preuves du temps

Couvre l'analyse de la pire complexité temporelle pour les algorithmes et la complexité temporelle avec des nombres réels et des entiers.