Complexité grand O

Que signifie 'complexité algorithmique' ?

C'est une mesure de l'efficacité d'un algorithme en termes de temps et d'espace requis.

Complexité temporelle →

Elle évalue le temps d'exécution d'un algorithme pour des entrées de taille n.

Vrai ou faux : Tous les algorithmes ont la même complexité.

Faux. Chaque algorithme a une complexité propre, variant selon l'implémentation et les données.

Que représente 'n' dans la complexité ?

C'est généralement la taille de l'entrée de l'algorithme, comme le nombre d'éléments à traiter.

L'impact d'une complexité O(n) ?

L'algorithme augmente linéairement avec la taille des données. Exemple : un parcours d'un tableau.

Comparer O(1) et O(n) :

O(1) : Temps constant, peu importe la taille. O(n) : Temps linéaire, dépend de n.

Exemple d'algorithme avec O(n²) ?

L'algorithme de tri à bulles, qui compare chaque élément avec tous les autres.

Que signifie 'complexité spatiale' ?

C'est la quantité de mémoire utilisée par un algorithme en fonction de la taille de l'entrée.

Quand utiliser O(log n) ?

Pour les algorithmes qui divisent continuellement les données, comme la recherche binaire.

Remplissez le blanc : O(n log n) est typique pour ___ .

les algorithmes de tri efficaces comme le tri fusion ou le tri rapide.

Qu'est-ce que la notation asymptotique ?

C'est une façon de décrire la complexité en fonction de la taille d'entrée, en se concentrant sur le comportement à long terme.

Vrai ou faux : O(n) est toujours meilleur que O(n²).

Vrai. O(n) est plus efficace que O(n²) pour de grandes valeurs de n.

Que représente O(2^n) ?

Une complexité exponentielle, typique pour des problèmes de combinatoire ou des algorithmes naïfs de recherche.

Citer un inconvénient des algorithmes O(n!) ?

Ils deviennent impraticables pour n > 10 en raison de la croissance rapide du temps d'exécution.

Cause → Effet : Augmenter la taille des données influence...

la complexité d'exécution d'un algorithme, souvent augmentant le temps de traitement.

Comparer O(n) et O(log n) :

O(n) : Croissance linéaire. O(log n) : Croissance logarithmique, plus rapide pour de grandes entrées.

Complexité temporelle

Mesure du temps d'exécution d'un algorithme en fonction de la taille des données.

Complexité spatiale

Mesure de l'espace mémoire utilisé par un algorithme durant son exécution.

O(1)

Complexité constante. Temps d'exécution ne dépend pas de la taille des données.

O(n)

Complexité linéaire. Temps d'exécution proportionnel à la taille des données.

O(n^2)

Complexité quadratique. Temps d'exécution augmente avec le carré de la taille des données.

Vrai ou faux: O(log n) est plus rapide que O(n)

Vrai. O(log n) croît plus lentement que O(n) pour de grandes valeurs de n.

O(n log n)

Complexité souvent rencontrée dans des algorithmes de tri comme le tri par fusion.

Exemple d'algorithme O(n^2)

Tri à bulles. Chaque élément est comparé avec tous les autres.

Cause -> Effet: augmentation des données

Augmente le temps d'exécution si la complexité est O(n).

O(2^n)

Complexité exponentielle. Très inefficace pour de grandes valeurs de n, comme dans le problème du voyageur.

Comparaison: O(n) vs O(n^2)

O(n) est plus efficace que O(n^2) pour des grandes entrées de données.

O(n + m)

Complexité pour les algorithmes traitant deux ensembles de données de tailles n et m.

Exemple de complexité O(log n)

Recherche binaire. Divise l'ensemble en deux à chaque étape.

Définition de la complexité polylogarithmique

Complexité de la forme O((log n)^k) pour un entier k.

Complexité exponentielle

Croissance rapide, souvent impraticable pour n > 20. Exemple: O(2^n).

Évaluation de la complexité globale

Complexité d'un algorithme se base sur la partie la plus lente, la plus dominante.

Vrai ou faux: O(n) et O(n + m) sont équivalents

Faux. O(n + m) prend en compte deux tailles différentes, plus rapide dans certains cas.

Complexité asymptotique

Comportement d'un algorithme pour des entrées de taille très grande.

Fill in the blank: O(n^3) est une complexité ____

cubique, souvent présente dans des algorithmes de traitement de matrices.

Types de complexité

Il existe deux types principaux de complexité dans les algorithmes : - **Complexité temporelle** : mesure le temps d'exécution en fonction de la taille des entrées. - **Complexité spatiale** : évalue la mémoire utilisée par l'algorithme pendant son exécution.

Notation grand O

La notation grand O décrit la complexité asymptotique d'un algorithme, en se concentrant sur son comportement à l'infini.

Vérité ou faux : O(n) est plus rapide que O(n^2).

Vrai. O(n) croît linéairement, tandis que O(n^2) croît quadratiquement, ce qui est plus lent.

Définir O(1).

O(1) signifie que le temps d'exécution reste constant, indépendamment de la taille des données d'entrée.

O(n log n)

C'est la complexité typique des algorithmes de tri efficaces comme le tri rapide ou le tri par fusion.

Remplir le blanc : O(n^3) est un exemple de ____.

complexité cubique.

Comparer O(n) et O(log n).

O(log n) est plus rapide que O(n). La complexité logarithmique est plus efficace pour les grandes entrées.

Exemple de O(n^2)

L'algorithme de tri à bulles a une complexité O(n^2) dans le pire des cas.

Quel est le but de la notation grand O ?

Évaluer et comparer l'efficacité des algorithmes en fonction de la taille de l'entrée.

O(2^n)

C'est une complexité exponentielle, souvent associée à des algorithmes de recherche exhaustive, comme le problème du voyageur de commerce.

Vérité ou faux : O(n) = O(2n).

Vrai. Les constantes multipliées ne changent pas la classe de complexité.

Définir O(n!).

O(n!) représente une complexité factorielle, courante dans les problèmes de permutations et de combinaisons.

Cause → effet : Si une entrée double, quel est l'effet sur O(n) ?

Le temps d'exécution double également, car O(n) est linéaire.

Quel est l'avantage de la notation grand O ?

Elle permet d'ignorer les constantes et les termes non dominants pour se concentrer sur la croissance asymptotique.

Comparer O(n) et O(√n).

O(√n) est plus rapide que O(n). La racine carrée croît moins vite qu'une ligne droite.

Remplir le blanc : L'algorithme de recherche binaire a une complexité de ___.

O(log n).

O(n^2) vs O(n log n)

O(n log n) est généralement plus efficace pour de grandes entrées que O(n^2).

Quel est l'inconvénient de O(2^n) ?

Elle devient rapidement impraticable pour les tailles d'entrée même modérées en raison de sa croissance rapide.

Définir O(log n).

O(log n) indique que le temps d'exécution diminue en fonction de la taille d'entrée, comme dans la recherche binaire.

O(n) est souvent associée à quel type d'algorithme ?

Les algorithmes de parcours, comme la recherche linéaire, qui traitent chaque élément une fois.

Que signifie la notation grand O ?

La notation grand O permet de décrire la complexité asymptotique d'un algorithme, en indiquant son comportement à l'infini. Elle se concentre sur la partie la plus significative de la fonction de temps ou d'espace, ignorant les constantes et les termes non dominants.

Recherche linéaire → définition

Algorithme qui parcourt chaque élément d'une liste pour trouver un élément cible. Complexité : $\displaystyle O(n)$.

Tri à bulles → complexité

Algorithme de tri simple. Complexité dans le pire des cas : $\displaystyle O(n^2)$.

Vrai ou faux: le tri rapide est toujours $\displaystyle O(n^2)$

Faux. Complexité moyenne : $\displaystyle O(n imes ext{log}(n))$, meilleur cas : $\displaystyle O(n)$.

Complexité d'un tri fusion

Tri fusion a une complexité de $\displaystyle O(n imes ext{log}(n))$, efficace pour de grandes listes.

Recherche binaire → conditions

Doit être appliquée sur une liste triée. Complexité : $\displaystyle O( ext{log}(n))$.

Exemple de parcours d'arbre

Parcours en profondeur : $\displaystyle O(n)$, où $\displaystyle n$ est le nombre de nœuds.

Comparaison entre tri par insertion et tri par sélection

Tri par insertion : $\displaystyle O(n^2)$. Tri par sélection : $\displaystyle O(n^2)$. Insertion est souvent plus rapide en pratique.

Remplir le blanc: Complexité du Dijkstra ?

$\displaystyle O((V + E) imes ext{log}(V))$, où $\displaystyle V$ est le nombre de sommets et $\displaystyle E$ le nombre d'arêtes.

Complexité d'un algorithme de Floyd-Warshall

Complexité : $\displaystyle O(n^3)$, utilisé pour trouver les plus courts chemins dans un graphe.

Comparer complexité : Kruskal vs Prim

Kruskal : $\displaystyle O(E imes ext{log}(E))$. Prim : $\displaystyle O(E + V imes ext{log}(V))$.

Complexité d'un algorithme de backtracking

Dépend du problème, souvent exponentielle : $\displaystyle O(n!)$ dans le cas des permutations.

Exemple de complexité dans un algorithme glouton

Problème du sac à dos : complexe avec des solutions approximatives, souvent $\displaystyle O(n imes W)$.

Vrai ou faux: la recherche exhaustive est toujours optimale

Vrai, mais inefficace pour des grands ensembles de données. Complexité : $\displaystyle O(n!)$.

Exemple d'algorithme de programmation dynamique

Calcul du nombre de Fibonacci. Complexité : $\displaystyle O(n)$ avec mémorisation.

Complexité de l'algorithme A*

Complexité dépend de la heuristique, en général : $\displaystyle O(E)$. E est le nombre d'arêtes.

Graphes : complexité de BFS

Complexité du parcours en largeur : $\displaystyle O(V + E)$, avec V sommets et E arêtes.