Qu'est-ce que la notation Big O? L'utilisez vous? [dupliquer]

Question

    

Cette question a déjà une réponse ici:

    

        
•              Qu'est-ce qu'une explication en anglais simple de & # 8220; Big O & # 8221; notation?                                      39 réponses                          
    

    

Qu'est-ce que la notation Big O? L'utilisez-vous?

J'ai raté cette classe universitaire, je suppose: D

Quelqu'un l'utilise-t-il et donne-t-il des exemples concrets d'utilisation?

Voir aussi:

Big-O pour les huit ans?
Big O, comment calculez-vous / approximez-vous?
Avez-vous appliqué la théorie de la complexité de calcul dans la vie réelle?

Answer 1

Une chose importante que la plupart des gens oublient lorsqu’on parle de Big-O, c’est pourquoi je ressens le besoin de mentionner que:

Vous ne pouvez pas utiliser Big-O pour comparer la vitesse de deux algorithmes. Big-O ne dit que combien de temps un algorithme ralentira (environ) si vous doublez le nombre d’éléments traités, ou combien il sera plus rapide si vous réduisez ce nombre de moitié.

Cependant, si vous avez deux algorithmes totalement différents et que l'un ( A ) est O (n ^ 2) et l'autre ( B ) est O (log n) , on ne dit pas que A est plus lent que B . En fait, avec 100 éléments, A pourrait être dix fois plus rapide que B . Cela dit seulement qu'avec 200 éléments, A augmentera plus lentement du facteur n ^ 2 et B augmentera plus lentement du facteur log n . Donc, si vous comparez les deux et que vous savez combien de temps A faut pour traiter 100 éléments, et combien de temps B a besoin pour les mêmes 100 éléments, et A est plus rapide que B , vous pouvez calculer à quelle quantité d'éléments B dépassera A en vitesse (comme la vitesse de < code> B diminue beaucoup plus lentement que celui de A , il dépassera A tôt ou tard, c’est certain).

Answer 2

La notation Big O désigne le facteur limitant d’un algorithme. C’est une expression simplifiée de la façon dont le temps d’exécution d’un algorithme varie en fonction de l’entrée.

Par exemple (en Java):

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

Maintenant, réfléchissez à ce que cela fait réellement. Il passe en revue tous les caractères d’entrée et les ajoute. Cela semble simple. Le problème est que la chaîne est immuable . Ainsi, chaque fois que vous ajoutez une lettre à la chaîne, vous devez créer une nouvelle chaîne. Pour ce faire, vous devez copier les valeurs de l'ancienne chaîne dans la nouvelle chaîne et ajouter le nouveau caractère.

Cela signifie que vous allez copier la première lettre n fois où n est le nombre de caractères de l'entrée. Vous allez copier le caractère n-1 , il y aura donc au total des copies de (n-1) (n / 2) .

Ceci est (n ^ 2-n) / 2 et pour la notation Big O, nous utilisons uniquement le facteur de magnitude le plus élevé (généralement) et supprimons les constantes multipliées par ce résultat. O (n ^ 2) .

Utiliser quelque chose comme un StringBuilder suivra les lignes de O (nLog (n)). Si vous calculez le nombre de caractères au début et définissez la capacité du StringBuilder , vous pouvez obtenir le code O (n) .

Donc, si nous avions 1000 caractères en entrée, le premier exemple effectuerait environ un million d'opérations, StringBuilder en exécuterait 10 000 et le StringBuilder avec setCapacity effectuerait 1000 opérations pour faire la même chose. C’est une estimation approximative, mais la notation O (n) concerne des ordres de grandeurs, pas une exécution exacte.

Ce n’est pas quelque chose que j’utilise régulièrement. Cependant, je ne cesse de penser au meilleur algorithme pour faire quelque chose.

Answer 3

Une question très similaire a déjà été posée à l'adresse Big-O pour les huit ans? . J'espère que les réponses y répondront, bien que le correspondant à la question ait quelques connaissances mathématiques à son sujet, mais que vous ne l'ayez peut-être pas, alors clarifiez si vous avez besoin d'explications plus complètes.

Answer 4

Chaque programmeur doit savoir ce qu’est la notation Big O, comment elle s’applique aux actions ayant des structures de données et des algorithmes communs (et ainsi choisir le bon DS et l’algorithme correspondant au problème qu’ils résolvent), et comment le calculer pour leur propres algorithmes.

1) C'est un ordre de mesure de l'efficacité d'un algorithme lorsque vous travaillez sur une structure de données.

2) Des actions comme 'add' / 'sort' / 'remove' peuvent prendre différentes durées avec différentes structures de données (et algorithmes), par exemple 'add' et 'find' sont O (1) pour un hashmap , mais O (log n) pour un arbre binaire. Le tri est O (nlog n) pour QuickSort, mais O (n ^ 2) pour BubbleSort, lorsqu’il s’agit d’un tableau simple.

3) Les calculs peuvent être effectués en regardant la profondeur de boucle de votre algorithme en général. Pas de boucles, O (1), boucles itérantes sur tout le set (même si elles éclatent à un moment donné) O (n). Si la boucle réduit de moitié l'espace de recherche à chaque itération? O (log n). Prenez le plus haut O () pour une séquence de boucles et multipliez le O () lorsque vous imbriquez des boucles.

Oui, c'est plus complexe que ça. Si vous êtes vraiment intéressé, procurez-vous un manuel.

Answer 5

La notation 'Big-O' est utilisée pour comparer les taux de croissance de deux fonctions d'une variable (disons n) car n devient très grand. Si la fonction f croît beaucoup plus rapidement que la fonction g, nous dirons que g = O (f) implique que pour n assez grand, f sera toujours toujours supérieur à g jusqu'à un facteur d'échelle.

Il s’avère que c’est une idée très utile en informatique et en particulier dans l’analyse des algorithmes, car nous nous intéressons souvent précisément aux taux de croissance des fonctions qui représentent, par exemple, le temps pris par deux algorithmes différents. Très grossièrement, nous pouvons déterminer qu'un algorithme avec le temps d'exécution t1 (n) est plus efficace qu'un algorithme avec le temps d'exécution t2 (n) si t1 = O (t2) pour un assez grand n qui est typiquement la "taille" de le problème - comme la longueur du tableau ou le nombre de nœuds dans le graphique ou autre.

Cette stipulation, qui devient assez grande, nous permet de tirer beaucoup de trucs utiles. Le plus souvent utilisé est peut-être que vous pouvez simplifier les fonctions jusqu’à leur croissance la plus rapide. Par exemple, n ^ 2 + n = O (n ^ 2), car si n devient suffisamment grand, le terme n ^ 2 devient tellement plus grand que n que le terme n est pratiquement insignifiant. Nous pouvons donc le laisser tomber de considération.

Cependant, cela signifie que la notation big-O est moins utile pour les petits n, car les termes à croissance lente que nous avons oubliés sont encore suffisamment importants pour affecter le temps d'exécution.

Nous avons maintenant un outil de comparaison des coûts de deux algorithmes différents et un raccourci pour dire que l’un est plus rapide ou plus lent que l’autre. On peut abuser de la notation Big-O, ce qui est dommage car elle est déjà suffisamment imprécise! Il existe des termes équivalents pour dire qu'une fonction croît moins vite qu'une autre et que deux fonctions croissent au même rythme.

Oh, et est-ce que je l'utilise? Oui, tout le temps, lorsque je constate à quel point mon code est efficace, il donne une très bonne approximation du coût.

Answer 6

L'intelligence " derrière Big-O

Imaginez un "concours" entre deux fonctions sur x, lorsque x approche l'infini: f (x) et g (x).

Maintenant, si à un moment donné (une x), une fonction a toujours une valeur plus élevée que l'autre, appelons cette fonction "plus vite" que l'autre.

Donc, par exemple, si pour chaque x > 100 vous voyez que f (x) > g (x), alors f (x) est "plus rapide" que g (x).

Dans ce cas, nous dirions g (x) = O (f (x)). f (x) pose une sorte de "limite de vitesse" des sortes pour g (x), puisqu’il finit par le laisser et le laisser pour de bon.

Ce n'est pas exactement la définition de la notation big-O , qui indique également que f (x) doit seulement être plus grand que C * g (x) pour une constante C (ce qui est juste une autre façon de dire que vous ne pouvez pas aider g (x) à gagner le concours en le multipliant par un facteur constant - f (x) gagnera toujours à la fin). La définition formelle utilise également des valeurs absolues. Mais j'espère avoir réussi à le rendre intuitif.

Answer 7

Il peut également être intéressant de considérer que la complexité de nombreux algorithmes repose sur plusieurs variables, en particulier dans les problèmes multidimensionnels. Par exemple, j'ai récemment dû écrire un algorithme pour ce qui suit. Avec un ensemble de n points et de m polygones, extrayez tous les points situés dans l'un des polygones. La complexité est basée sur deux variables connues, n et m, et l’inconnue du nombre de points dans chaque polygone. La grande notation O est ici un peu plus complexe que O (f (n)) ou même O (f (n) + g (m)). Big O est bon quand vous avez affaire à un grand nombre d’articles homogènes, mais ne vous attendez pas à ce que ce soit toujours le cas.

Il convient également de noter que le nombre réel d’itérations sur les données dépend souvent de celles-ci. Quicksort est généralement rapide, mais donnez-lui des données pré-triées et cela ralentira. Mes points et mes polygones se sont alogoriths assez vite, proche de O (n + (m log (m)), sur la base de la connaissance préalable de l’organisation probable des données et de la taille relative de n et m. mal sur des données organisées au hasard de différentes tailles relatives.

Une dernière chose à considérer est qu’il existe souvent un compromis direct entre la vitesse d’un algorithme et la quantité d’espace qu’il utilise. Le Le tri des trous de pigeons en est un très bon exemple. Pour revenir à mes points et polygones, disons que tous mes polygones étaient simples et rapides à dessiner, et je pouvais les dessiner remplis à l'écran, disons en bleu, dans un laps de temps déterminé. Donc, si je dessine mes m polygones sur un écran noir, cela prendrait O (m) temps. Pour vérifier si l'un de mes n points était dans un polygone, je vérifie simplement si le pixel à cet endroit est vert ou noir. La vérification est donc O (n) et l'analyse totale est O (m + n). L’inconvénient, c’est bien sûr que j’ai besoin d’un stockage quasi infini si j’ai affaire à des coordonnées du monde réel précises au millimètre près ...

Answer 8

Il peut également être utile de considérer le temps amorti , plutôt que dans le pire des cas. Cela signifie, par exemple, que si vous exécutez l'algorithme n fois, ce sera O (1) en moyenne, mais cela pourrait parfois être pire.

Un bon exemple est une table dynamique, qui est essentiellement un tableau qui s’agrandit au fur et à mesure que vous y ajoutez des éléments. Une implémentation naïve augmenterait la taille du tableau de 1 pour chaque élément ajouté, ce qui signifie que tous les éléments doivent être copiés à chaque fois qu'un nouvel élément est ajouté. Cela entraînerait un algorithme O (n ² ) si vous concaténiez une série de tableaux utilisant cette méthode. Une autre solution consiste à doubler la capacité de la matrice chaque fois que vous avez besoin de plus de stockage. Bien que l’ajout soit une opération O (n) , il vous suffira parfois de copier des éléments O (n) pour chaque n élément ajouté, l’opération est donc en moyenne O (1) . C’est ainsi que des choses comme StringBuilder ou std :: vector sont mises en oeuvre.

Answer 9

Qu'est-ce que la notation Big O?

La notation Big O est une méthode permettant d’exprimer la relation entre de nombreuses étapes requises par un algorithme et relatives à la taille des données d’entrée. Ceci est appelé la complexité algorithmique. Par exemple, le tri d’une liste de taille N à l’aide du tri à bulles prend 0 étape (N ^ 2).

Est-ce que j'utilise la notation Big O?

J'utilise parfois la notation Big O pour transmettre la complexité algorithmique à d'autres programmeurs. J'utilise la théorie sous-jacente (par exemple, les techniques d'analyse Big O) tout le temps quand je pense aux algorithmes à utiliser.

Exemples concrets?

J'ai utilisé la théorie de l'analyse de complexité pour créer des algorithmes destinés à des structures de données de pile efficaces ne nécessitant aucune réallocation de mémoire et prenant en charge le temps moyen d'indexation O (N). J'ai utilisé la notation Big O pour expliquer l'algorithme à d'autres personnes. J'ai également utilisé l'analyse de complexité pour comprendre quand le tri linéaire temporel O (N) est possible.

Answer 10

À partir de Wikipedia .....

La notation Big O est utile lors de l'analyse d'efficacité des algorithmes. Par exemple, le temps (ou le nombre d’étapes) qu’il faut pour résoudre un problème de taille n peut être considéré comme étant T (n) = 4n² - 2n + 2.

Comme n grandit, le terme n² finira par dominer, de sorte que tous les autres termes peuvent être négligés - par exemple, lorsque n = 500, le terme 4n² est 1000 fois plus grand que le terme 2n. Ignorer ce dernier aurait un effet négligeable sur la valeur de l'expression dans la plupart des cas.

Évidemment je ne l'ai jamais utilisé ..

Answer 11

Vous devriez pouvoir évaluer la complexité d'un algorithme. Ceci, combiné à la connaissance du nombre d’éléments requis, peut vous aider à déterminer s’il est mal adapté à sa tâche.

Answer 12

Il indique le nombre d'itérations qu'un algorithme a dans le pire des cas.

pour rechercher un élément dans une liste, vous pouvez parcourir la liste jusqu'à ce que vous obteniez l'élément. Dans le pire des cas, l'élément se trouve à la dernière place.

Disons qu'il y a n éléments dans la liste. Dans le pire des cas, vous prenez n itérations. Dans la notation Big O, il s’agit de O (n).

Cela indique factuellement l'efficacité d'un algorithme.