algorithmNotation Big-O


Remarques

Définition

La notation Big-O est au cœur d'une notation mathématique, utilisée pour comparer le taux de convergence des fonctions. Soit n -> f(n) et n -> g(n) fonctions définies sur les nombres naturels. On dit alors que f = O(g) si et seulement si f(n)/g(n) est borné quand n s'approche de l'infini. En d'autres termes, f = O(g) si et seulement s'il existe une constante A, telle que pour tout n, f(n)/g(n) <= A

En réalité, la portée de la notation Big-O est un peu plus large en mathématiques, mais pour simplifier, je l'ai réduite à ce qui est utilisé dans l'analyse de la complexité des algorithmes: les fonctions définies sur les à l'infini.

Qu'est-ce que ça veut dire ?

Prenons le cas de f(n) = 100n^2 + 10n + 1 et g(n) = n^2 . Il est clair que ces deux fonctions tendent à l'infini lorsque n tend vers l'infini. Mais parfois, connaître la limite ne suffit pas, et nous voulons également connaître la vitesse à laquelle les fonctions se rapprochent de leur limite. Des notions telles que Big-O permettent de comparer et de classer les fonctions selon leur vitesse de convergence.

Voyons si f = O(g) en appliquant la définition. Nous avons f(n)/g(n) = 100 + 10/n + 1/n^2 . Depuis 10/n est 10 lorsque n est égal à 1 et diminue, et que 1/n^2 est égal à 1 lorsque n est égal à 1 et est également diminué, on a F f(n)/g(n) <= 100 + 10 + 1 = 111 . La définition est satisfaite car nous avons trouvé une limite de f(n)/g(n) (111) et donc f = O(g) (on dit que f est un Big-O de n^2 ).

Cela signifie que f tend vers l'infini approximativement à la même vitesse que g. Cela peut sembler étrange à dire, car nous avons trouvé que f est au plus 111 fois plus grand que g, ou en d'autres termes lorsque g augmente de 1, f augmente d'au plus 111. Il peut sembler croissant que 111 fois plus rapide n'est pas "approximativement la même vitesse". Et en effet, la notation Big-O n'est pas un moyen très précis de classer la vitesse de convergence des fonctions. C'est pourquoi, en mathématiques, nous utilisons la relation d'équivalence lorsque nous voulons une estimation précise de la vitesse. Mais pour séparer les algorithmes dans les grandes classes de vitesse, Big-O est suffisant. Nous n'avons pas besoin de séparer les fonctions qui se développent un nombre de fois plus rapide que les autres, mais uniquement des fonctions qui augmentent infiniment plus rapidement les unes que les autres. Par exemple si on prend h(n) = n^2*log(n) , on voit que h(n)/g(n) = log(n) qui tend vers l'infini avec n donc h n'est pas O (n ^ 2), car h pousse infiniment plus vite que n ^ 2.

Maintenant, je dois faire une remarque: vous avez peut-être remarqué que si f = O(g) et g = O(h) , alors f = O(h) . Par exemple, dans notre cas, nous avons f = O(n^3) et f = O(n^4) ... Dans l’analyse de la complexité de l’algorithme, nous disons fréquemment que f = O(g) signifie que f = O(g) et g = O(f) , ce qui peut être compris comme "g est le plus petit Big-O pour f". En mathématiques, nous disons que ces fonctions sont les Big Thetas les unes des autres.

Comment est-ce utilisé ?

Lorsque nous comparons les performances de l'algorithme, nous nous intéressons au nombre d'opérations effectuées par un algorithme. Cela s'appelle la complexité du temps . Dans ce modèle, nous considérons que chaque opération de base (addition, multiplication, comparaison, affectation, etc.) prend un temps fixe et nous comptons le nombre de ces opérations. Nous pouvons généralement exprimer ce nombre en fonction de la taille de l'entrée, que nous appelons n. Et malheureusement, ce nombre augmente généralement à l'infini avec n (si ce n'est pas le cas, nous disons que l'algorithme est O (1)). Nous séparons nos algorithmes en grandes classes de vitesse définies par Big-O: lorsque nous parlons d'un "algorithme O (n ^ 2)", nous voulons dire que le nombre d'opérations qu'il exécute, exprimé en fonction de n, est un O ( n ^ 2). Ceci dit que notre algorithme est approximativement aussi rapide qu'un algorithme qui ferait un nombre d'opérations égal au carré de la taille de son entrée, ou plus rapide . La partie "ou plus rapide" est là parce que j'ai utilisé Big-O au lieu de Big-Theta, mais généralement, les gens diront Big-O pour Big-Theta.

Lors du comptage d'opérations, nous considérons généralement le pire des cas: par exemple, si nous avons une boucle qui peut s'exécuter au plus n fois et qui contient 5 opérations, le nombre d'opérations que nous comptons est 5n. Il est également possible de considérer la complexité moyenne des cas.

Note rapide: un algorithme rapide est celui qui effectue peu d'opérations, donc si le nombre d'opérations augmente à l'infini plus rapidement , alors l'algorithme est plus lent : O (n) est meilleur que O (n ^ 2).

Nous sommes aussi parfois intéressés par la complexité spatiale de notre algorithme. Pour cela, considérons le nombre d'octets en mémoire occupés par l'algorithme en fonction de la taille de l'entrée, et utilisons Big-O de la même manière.

Notation Big-O Exemples Liés