Notations asymptotiques et analyse Apriori
Dans la conception de l'algorithme, l'analyse de la complexité d'un algorithme est un aspect essentiel. La complexité algorithmique est principalement préoccupée par ses performances, sa vitesse ou sa lenteur.
La complexité d'un algorithme décrit l'efficacité de l'algorithme en termes de quantité de mémoire nécessaire pour traiter les données et de temps de traitement.
La complexité d'un algorithme est analysée selon deux perspectives: Time et Space.
Complexité temporelle
C'est une fonction décrivant le temps nécessaire pour exécuter un algorithme en fonction de la taille de l'entrée. «Temps» peut signifier le nombre d'accès à la mémoire effectués, le nombre de comparaisons entre les entiers, le nombre de fois qu'une boucle interne est exécutée, ou une autre unité naturelle liée à la quantité de temps réel que l'algorithme prendra.
Complexité spatiale
C'est une fonction décrivant la quantité de mémoire qu'un algorithme prend en termes de taille d'entrée de l'algorithme. On parle souvent de mémoire "supplémentaire" nécessaire, sans compter la mémoire nécessaire pour stocker l'entrée elle-même. Encore une fois, nous utilisons des unités naturelles (mais de longueur fixe) pour mesurer cela.
La complexité de l'espace est parfois ignorée parce que l'espace utilisé est minimal et / ou évident, mais parfois cela devient un problème aussi important que le temps.
Notations asymptotiques
Le temps d'exécution d'un algorithme dépend du jeu d'instructions, de la vitesse du processeur, de la vitesse d'E / S du disque, etc. Par conséquent, nous estimons l'efficacité d'un algorithme de manière asymptotique.
La fonction temporelle d'un algorithme est représentée par T(n), où n est la taille d'entrée.
Différents types de notations asymptotiques sont utilisés pour représenter la complexité d'un algorithme. Les notations asymptotiques suivantes sont utilisées pour calculer la complexité en temps d'exécution d'un algorithme.
O - Grand Oh
Ω - Gros oméga
θ - Gros thêta
o - Petit Oh
ω - Petit oméga
O: Limite supérieure asymptotique
«O» (Big Oh) est la notation la plus couramment utilisée. Une fonctionf(n) peut être représenté est l'ordre de g(n) C'est O(g(n)), s'il existe une valeur d'entier positif n comme n0 et une constante positive c tel que -
$ f (n) \ leqslant cg (n) $ pour $ n> n_ {0} $ dans tous les cas
Par conséquent, la fonction g(n) est une limite supérieure pour la fonction f(n), comme g(n) pousse plus vite que f(n).
Exemple
Considérons une fonction donnée, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considérant $ g (n) = n ^ 3 $,
$ f (n) \ leqslant 5.g (n) $ pour toutes les valeurs de $ n> 2 $
D'où la complexité de f(n) peut être représenté par $ O (g (n)) $, c'est-à-dire $ O (n ^ 3) $
Ω: Limite inférieure asymptotique
On dit que $ f (n) = \ Omega (g (n)) $ quand il existe une constante c que $ f (n) \ geqslant cg (n) $ pour toute valeur suffisamment grande de n. Icinest un entier positif. Cela signifie la fonctiong est une borne inférieure pour la fonction f; après une certaine valeur den, f ne descendra jamais en dessous g.
Exemple
Considérons une fonction donnée, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.
Considérant $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ pour toutes les valeurs de $ n> 0 $.
D'où la complexité de f(n) peut être représenté par $ \ Omega (g (n)) $, c'est-à-dire $ \ Omega (n ^ 3) $
θ: lié serré asymptotique
On dit que $ f (n) = \ theta (g (n)) $ quand il existe des constantes c1 et c2 que $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ pour toute valeur suffisamment grande de n. Icin est un entier positif.
Cela signifie la fonction g est une limite étroite pour la fonction f.
Exemple
Considérons une fonction donnée, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considérant $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ pour toutes les grandes valeurs de n.
D'où la complexité de f(n) peut être représenté par $ \ theta (g (n)) $, c'est-à-dire $ \ theta (n ^ 3) $.
O - Notation
La limite supérieure asymptotique fournie par O-notationpeut ou non être asymptotiquement serré. La borne $ 2.n ^ 2 = O (n ^ 2) $ est asymptotiquement serrée, mais la borne $ 2.n = O (n ^ 2) $ ne l'est pas.
Nous utilisons o-notation pour désigner une limite supérieure qui n'est pas asymptotiquement serrée.
Nous définissons formellement o(g(n)) (peu-oh de g de n) comme l'ensemble f(n) = o(g(n)) pour toute constante positive $ c> 0 $ et il existe une valeur $ n_ {0}> 0 $, telle que $ 0 \ leqslant f (n) \ leqslant cg (n) $.
Intuitivement, dans le o-notation, la fonction f(n) devient insignifiant par rapport à g(n) comme ns'approche de l'infini; C'est,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$
Exemple
Considérons la même fonction, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considérant $ g (n) = n ^ {4} $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$
D'où la complexité de f(n) peut être représenté par $ o (g (n)) $, c'est-à-dire $ o (n ^ 4) $.
ω - Notation
Nous utilisons ω-notationpour désigner une borne inférieure qui n'est pas asymptotiquement serrée. Cependant, formellement, nous définissonsω(g(n)) (petit-oméga de g de n) comme l'ensemble f(n) = ω(g(n)) pour toute constante positive C > 0 et il existe une valeur $ n_ {0}> 0 $, telle que $ 0 \ leqslant cg (n) <f (n) $.
Par exemple, $ \ frac {n ^ 2} {2} = \ omega (n) $, mais $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. La relation $ f (n) = \ omega (g (n)) $ implique que la limite suivante existe
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$
C'est, f(n) devient arbitrairement grand par rapport à g(n) comme n s'approche de l'infini.
Exemple
Considérons la même fonction, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
Considérant $ g (n) = n ^ 2 $,
$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$
D'où la complexité de f(n) peut être représenté par $ o (g (n)) $, c'est-à-dire $ \ omega (n ^ 2) $.
Analyse Apriori et Apostiari
L'analyse Apriori signifie que l'analyse est effectuée avant de l'exécuter sur un système spécifique. Cette analyse est une étape où une fonction est définie à l'aide d'un modèle théorique. Par conséquent, nous déterminons la complexité temporelle et spatiale d'un algorithme en regardant simplement l'algorithme plutôt que de l'exécuter sur un système particulier avec une mémoire, un processeur et un compilateur différents.
L'analyse Apostiari d'un algorithme signifie que nous effectuons l'analyse d'un algorithme uniquement après l'avoir exécuté sur un système. Cela dépend directement du système et des changements d'un système à l'autre.
Dans une industrie, nous ne pouvons pas effectuer d'analyse Apostiari car le logiciel est généralement conçu pour un utilisateur anonyme, qui l'exécute sur un système différent de ceux présents dans l'industrie.
Dans Apriori, c'est la raison pour laquelle nous utilisons des notations asymptotiques pour déterminer la complexité du temps et de l'espace à mesure qu'elles changent d'un ordinateur à l'autre; cependant, asymptotiquement, ils sont identiques.