Comment peut-on savoir que la notation de l'analyse de la complexité du temps à utiliser?

Question

Dans la plupart des classes d'algorithme d'introduction, notations comme O $ $ (Big O) et $ \ theta $ sont introduits, et un étudiant apprendrait généralement d'utiliser l'un de ceux-ci pour trouver la complexité du temps.

Cependant, il existe d'autres notations, comme $ o $, $ \ Omega $ et $ \ omega $. Y a-t-il des scénarios spécifiques où l'on notation serait préférable à l'autre?

Answer 1

Vous faites référence à la Landau notation . Ils ne sont pas des symboles différents pour la même chose, mais ont tout à fait différentes significations. Lequel est « préférable » dépend entièrement de la déclaration souhaitée.

$ f \ in \ cal {O} (g) $ signifie que $ f $ au plus croît aussi vite que $ g $, asymptotiquement et jusqu'à un facteur constant; penser comme $ \ leq $. $ F \ in o (g) $ est la forme plus sévère, à savoir $ <$.

$ f \ in \ Omega (g) $ a le sens symétrique: $ f au moins $ croît aussi vite que $ g $. $ \ Omega $ est son cousin plus stricte. Vous pouvez voir que $ f \ in \ Omega (g) $ équivaut à $ g \ in \ cal {O} (f) $.

$ f \ in \ Theta (g) $ signifie que $ f $ croît à peu près aussi rapide que g $ $; formellement $ f \ in \ cal {O} (g) \ cap \ Omega (g) $. $ F \ sim $ g (égalité asymptotique) est sa forme plus forte. Nous souvent dire $ \ theta $ lorsque nous utilisons $ \ cal {O} $.

Notez comment $ \ cal {O} (g) $ et ses frères et sœurs sont des classes de fonction . Il est important d'être très conscients et leurs définitions précises - qui peuvent varier en fonction de qui parle - lors d'un « Arithmétique » avec eux.

Lorsque la preuve des choses, prendre soin de travailler avec votre définition précise. Il existe plusieurs définitions pour les symboles Landau autour (tous avec la même intuition de base), dont certains sont équivalents sur certains jeux sur les fonctions, mais pas sur d'autres.

Lecture suggérée:

• Quelles sont les règles pour le signe égal avec grand-O et peu o?
• Fonctions de tri par la croissance asymptotique
• Comment O et O concernent pire et le meilleur des cas?
• Nested Big O notation
• Définition de $ \ theta $ pour les fonctions négatives
• Quel est le sens de $ O (m + n) $?
  est O (mn) à la croissance "linéaire" ou "du second degré"?
• des termes Sums Landau revisité
• Qu'est-ce que grand O en tant que moyen pour un terme d'un rapport d'approximation?
• Toute autre question sur et asymptote landau notation que l'exercice.

Si vous êtes intéressé à utiliser la notation Landau de manière rigoureuse et son, vous pouvez être intéressé par les travaux récents de Rutanen et al. [1]. Ils formulent des critères nécessaires et suffisants pour la notation asymptotique que nous les utilisons dans Algorithmics, montrent que la définition commune ne les rencontrer et de fournir un (la, en fait) définition pratique.

---

1. Une définition générale de l'O-notation pour l'analyse d'algorithme par K. Rutanen et al. (2015)

Answer 2

Big O: borne supérieure

« Big O » ($ O $) est de loin le plus un commun. Lorsque vous analysez la complexité d'un algorithme, la plupart du temps, ce qui importe est d'avoir une borne supérieure à quelle vitesse la time¹ d'exécution augmente lorsque la taille de l'entrée augmente. Fondamentalement, nous voulons savoir que l'exécution de l'algorithme ne va pas prendre « trop longtemps ». Nous ne pouvons pas exprimer en unités de temps réel (secondes), car cela dépendra de la mise en œuvre précise (la façon dont est écrit le programme, la qualité du compilateur est, la vitesse du processeur de la machine est, ...). Donc, nous évaluons ce qui ne dépend pas de ces détails, ce qui est combien de temps il faut pour exécuter l'algorithme lorsque nous l'alimentons entrée plus. Et nous nous soucions surtout quand nous pouvons être sûrs que le programme est fait, alors qu'habituellement nous voulons savoir que cela prendra telle ou telle quantité de temps ou moins.

Dire qu'un algorithme a un temps d'exécution de O $ (f (n)) $ pour une taille d'entrée $ n $ signifie qu'il y $ K existe une constante $ tel que l'algorithme finalise dans au plus $ K \, f (n) $ étapes, à savoir la durée de fonctionnement de l'algorithme se développe au plus aussi vite que $ f $ (jusqu'à un facteur d'échelle). Constatant T $ (n) $ Le temps d'exécution de l'algorithme de la taille de l'entrée $ n $, $ O (n) $ informelle moyens $ T (n) \ le f (n) $ jusqu'à un facteur de mise à l'échelle.

Limite inférieure

Parfois, il est utile d'avoir plus d'informations qu'une borne supérieure. $ \ Omega $ est l'inverse de $ O $: il exprime qu'une fonction croît au moins aussi vite que l'autre. $ T (n) = \ Omega (g (n)) $ signifie que $ T (N) \ ge K 'g (n) $ pour une constante $ K' $, ou de le mettre de façon informelle, $ T (n) \ ge g (n) $ jusqu'à un facteur d'échelle.

Lorsque la durée de fonctionnement de l'algorithme peut être déterminé avec précision, $ \ theta $ combine et O $ $ $ \ Omega $: il exprime le fait que le taux de croissance d'une fonction est connu, jusqu'à un facteur d'échelle. $ T (n) = \ Theta (h (n)) $ signifie que $ K h (n) \ ge T (n) \ ge K 'h (n) $ pour certaines constantes $ K $ et K $' $. parlant Officieusement, $ T (n) \ h environ (n) $ jusqu'à un facteur d'échelle.

D'autres considérations

Le « petit » $ o $ et $ \ omega $ sont utilisés beaucoup moins souvent dans l'analyse de la complexité. Peu $ o $ est plus forte que grande $ O $; où O $ $ indique une croissance qui est pas plus rapide, $ o $ indique que la croissance est strictement plus lente. À l'inverse, $ \ omega $ indique strictement une croissance plus rapide.

J'ai été un peu informel dans la discussion ci-dessus. Wikipedia a des définitions formall et une approche plus mathématique.

Notez que l'utilisation du signe égal à $ T (n) = O (f (n)) et analogues $ est un abus de langage. Au sens strict, O $ (f (n)) $ est un ensemble de fonctions de la variable $ n $, et nous devrions écrire $ T \ O (f) $.

Exemple: certains algorithmes de tri

Comme cela est assez sec, laissez-moi vous donner un exemple. La plupart des algorithmes de tri ont un temps d'exécution pire cas du second degré, à savoir pour une entrée de taille $ n $, le temps d'exécution de l'algorithme est O $ (n ^ 2) $. Par exemple, sorte a un O $ (n ^ 2) $ temps d'exécution, parce que la sélection de la k $ $ e élément exige $ nk comparaisons de dollars, pour un total de n $ (n-1) / 2 comparaisons de $. En fait, le nombre de comparaisons est toujours exactement $ n (n-1) / 2 $, ce qui augmente à mesure que n $ ^ 2 $. Ainsi, nous pouvons être plus précis sur la complexité temporelle de sorte sélection:. Il est $ \ theta (n ^ 2) $

Maintenant, prenez href="http://en.wikipedia.org/wiki/Merge_sort">. Fusionner est également quadratique tri (O $ (n ^ 2) $). Cela est vrai, mais pas très précis. Tri par fusion, en fait, a une durée de O $ (n \: \ mathrm {} lg (n)) $ dans le pire des cas. Comme la sélection sorte, le flux de travail de sorte de fusion est essentiellement indépendant de la forme de l'entrée, et son temps d'exécution est toujours $ n \: \ mathrm {lg} (n) $ jusqu'à un facteur multiplicatif constant, à savoir qu'il est $ \ theta (n \: \ mathrm {} lg (n)). $

Ensuite, tenez compte quicksort. Quicksort est plus complex. Il est certainement $ O (n ^ 2) $. En outre, le pire des cas de quicksort est quadratique: pire des cas est $ \ theta (n ^ 2) $. Cependant, le meilleur des cas de quicksort (lorsque l'entrée est déjà triée) est linéaire: le mieux que nous pouvons dire pour une limite inférieure à QuickSort en général est $ \ Omega (n) $. Je ne répéterai pas la preuve, mais le moyenne complexité de quicksort (la moyenne pris en charge toutes les permutations possibles de l'entrée) est $ \ theta (n \: \ mathrm {} lg (n).) $

Il y a des résultats généraux sur la complexité des algorithmes de tri dans les paramètres communs. Supposons qu'un algorithme de tri ne peut comparer deux éléments à la fois, avec un oui ou pas de résultat (soit $ x \ le y $ ou $ x> y $). Ensuite, il est évident que tout le temps d'exécution de l'algorithme de tri est toujours $ \ Omega (n) $ (où est $ n $ le nombre d'éléments pour trier), car l'algorithme doit comparer tous les éléments au moins une fois de savoir où il s'adaptera . Cette borne peut être satisfaite, par exemple, si l'entrée est déjà triée et l'algorithme compare simplement chaque élément avec la suivante et les maintient dans l'ordre (qui est $ n-1 comparaisons de $). Ce qui est moins évident est que la maximale temps de fonctionnement est nécessairement $ \ Omega (n \: \ mathrm {} lg (n)) $. Il est possible que l'algorithme fera parfois moins comparaisons, mais il doit y avoir une constante $ K $ tel que pour toute taille d'entrée $ n $, il y a au moins une entrée sur laquelle l'algorithme fait plus de $ K n \ mathrm { } lg (n) $ comparaisons. L'idée de la preuve est de construire l'arbre de décision de l'algorithme, à savoir suivre les décisions de l'algorithme prend du résultat de chaque comparaison. Étant donné que chaque comparaison renvoie un oui ou aucun résultat, l'arbre de décision est un arbre binaire. Il y a $ n! $ Permutations possibles de l'entrée, et les besoins de l'algorithme pour distinguer entre tous, de sorte que la taille de l'arbre de décision est $ n! $. Étant donné que l'arbre est un arbre binaire, il faut une profondeur de $ \ theta (\ mathrm {lg} (n)!) = \ Theta (n \: \ mathrm {lg} (n)) $ pour répondre à tous ces nœuds. La profondeur est le nombre maximum de décisions que l'algorithme prend, si l'exécution de l'algorithme implique au moins ce nombre de comparaisons: la durée maximale est de $ \ Omega (n \: \ mathrm {lg} (n)). $

¹ _{ou autre consommation de ressources telles que l'espace mémoire. Dans cette réponse, je considère que le temps d'exécution.}

Answer 3

En général O $ est utilisé pour énoncer-limites supérieures (une estimation ci-dessus), tandis que $ \ Omega $ est utilisé pour l'état limites inférieures (une estimation par le bas), et $ \ theta $ est utilisé quand ils correspondent , auquel cas vous pouvez utiliser $ \ theta $ à leur place (habituellement) pour indiquer le résultat.