Séance de cours

Conception de l'algorithme: Analyse de complexité temporelle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre les algorithmes, le pseudo-code, les entrées de données, les sorties, les variables internes, les affectations et les instructions. Il traite également de l'analyse de la complexité temporelle à l'aide d'exemples et de notations comme n2, O(n) et f(n)=O(g(n)). L'instructeur montre comment calculer le temps qu'un algorithme prend pour exécuter pour différentes tailles d'entrée.

Source officielle

Concepts associés (28)

Complexité en temps

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.

Instructions par cycle

En architecture d'ordinateur, instructions par cycle d'horloge (instruction par cycle ou IPC) est un terme utilisé pour décrire un aspect de la performance d'un microprocesseur : le nombre moyen d'instructions exécutées pour chaque cycle du signal d'horloge. À ne pas confondre avec le nombre de cycles par instruction. Le nombre d'instructions par seconde d'un processeur peut être déterminé en multipliant l'IPC par la fréquence d'horloge (mesuré en cycles par seconde ou hertz) du microprocesseur en question.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Instructions par seconde

L'instruction par seconde (IPS) est une unité de mesure de la performance d'un système informatique. On l'exprime généralement en million d'instructions par seconde (MIPS). Le nombre d'opérations en virgule flottante par seconde (FLOPS) est également utilisé. Dans un processeur, une opération est exécutée par plusieurs types d'instructions déplacement, le calcul ou la comparaison. L'architecture du processeur est donc à prendre en compte en plus du nombre de MIPS associé, avant d'en déduire un quelconque indice de performance.

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Afficher plus

Séances de cours associées (64)

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.

Ingrédients de base des algorithmes

Couvre les éléments de base des algorithmes, y compris le traitement des données, les instructions et les structures de contrôle.

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Théorème principal : Analyse de complexité temporelle

Présente le théorème principal pour l'analyse de la complexité du temps de l'algorithme à travers la subdivision des problèmes et l'application de la formule.

Recherche d'algorithmes: Recherche de dichotomie

Explore les algorithmes de recherche de dichotomie, en analysant la complexité et les détails de mise en œuvre pour une recherche efficace dans les listes triées.

Afficher plus

Concepts associés (28)

Complexité en temps

Instructions par cycle

Computational complexity

Instructions par seconde

Théorie de la complexité (informatique théorique)

Afficher plus