Estimateur d'efficacité
Calculez la complexité temporelle des fonctions et des algorithmes.
Copiez cette invite dans notre Console de développeur pour l’essayer vous-même !
Contenu | |
---|---|
Système | Votre tâche est d’analyser la fonction ou l’algorithme fourni et de calculer sa complexité temporelle en utilisant la notation Big O. Expliquez votre raisonnement étape par étape, en décrivant comment vous êtes arrivé à la complexité temporelle finale. Considérez le pire des cas lors de la détermination de la complexité temporelle. Si la fonction ou l’algorithme contient plusieurs étapes ou des boucles imbriquées, fournissez la complexité temporelle pour chaque étape, puis donnez la complexité temporelle globale pour l’ensemble de la fonction ou de l’algorithme. Supposez que toutes les fonctions ou opérations intégrées utilisées ont une complexité temporelle de O(1), sauf indication contraire. |
Utilisateur | def example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k) |
Exemple de sortie
Pour analyser la complexité temporelle de la fonction donnée
example_function(n)
, nous allons la décomposer en étapes et considérer le pire des cas.Étape 1 : Analyse de la première boucle
for i in range(n): print(i)
Cette boucle itère
n
fois et effectue une opération en temps constant (print(i)
) à chaque itération. Par conséquent, la complexité temporelle de cette étape est O(n).Étape 2 : Analyse des boucles imbriquées
for j in range(n): for k in range(n): print(j, k)
La boucle externe itère
n
fois, et pour chaque itération, la boucle interne itère égalementn
fois. À chaque itération de la boucle interne, une opération en temps constant (print(j, k)
) est effectuée. Par conséquent, la complexité temporelle des boucles imbriquées est O(n * n) = O(n^2).Étape 3 : Combinaison des complexités temporelles
La fonctionexample_function(n)
se compose de deux étapes : la première boucle et les boucles imbriquées. La complexité temporelle globale est la somme des complexités temporelles de chaque étape.Complexité temporelle de la première boucle : O(n)
Complexité temporelle des boucles imbriquées : O(n^2)Pour déterminer la complexité temporelle globale, nous considérons le terme dominant, qui est le terme avec l’ordre de croissance le plus élevé. Dans ce cas, O(n^2) domine O(n).
Par conséquent, la complexité temporelle globale de la fonction
example_function(n)
est O(n^2).Dans le pire des cas, lorsque
n
est grand, les boucles imbriquées domineront le temps d’exécution et la fonction aura une complexité temporelle quadratique.