S'agit-il d'une «règle» appropriée pour identifier la notation «Big O» d'un algorithme?

J'en ai appris plus sur Big O Notation et comment le calculer en fonction de la façon dont un algorithme est écrit. Je suis tombé sur un ensemble intéressant de «règles» pour calculer la notation Big O d'un algorithme et je voulais voir si je suis sur la bonne voie ou à la dérive.

Notation Big O: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Notation Big O: N ²

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Notation Big O: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Notation Big O: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

Mes exemples et la notation suivante sont-ils corrects? Y a-t-il des notations supplémentaires dont je devrais être au courant?

Formellement, la notation big-O décrit le degré de complexité.

Pour calculer la notation big-O:

1. identifier la formule de la complexité de l'algorithme. Disons, par exemple, deux boucles avec une autre imbriquée à l'intérieur, puis trois autres boucles non imbriquées:2N² + 3N
2. supprimer tout sauf le terme le plus élevé: 2N²
3. supprimer toutes les constantes: N²

En d'autres termes, deux boucles avec une autre imbriquée à l'intérieur, puis trois autres boucles non imbriquées sont O (N²)

Cela suppose bien sûr que ce que vous avez dans vos boucles soit de simples instructions. Si vous avez par exemple sort()à l'intérieur de la boucle, vous devrez multiplier la complexité de la boucle par la complexité de l' sort()implémentation que votre langue / bibliothèque sous-jacente utilise.

Si vous voulez analyser ces algorithmes, vous devez définir // dostuff, car cela peut vraiment changer le résultat. Supposons que dostuff nécessite un nombre O (1) constant d'opérations.

Voici quelques exemples avec cette nouvelle notation:

Pour votre premier exemple, la traversée linéaire: c'est correct!

SUR):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Pourquoi est-il linéaire (O (n))? Lorsque nous ajoutons des éléments supplémentaires à l'entrée (tableau), la quantité d'opérations qui se produisent augmente proportionnellement au nombre d'éléments que nous ajoutons.

Donc, s'il faut une opération pour incrémenter un entier quelque part en mémoire, nous pouvons modéliser le travail que fait la boucle avec f (x) = 5x = 5 opérations supplémentaires. Pour 20 éléments supplémentaires, nous effectuons 20 opérations supplémentaires. Un seul passage d'un tableau a tendance à être linéaire. Il en va de même pour les algorithmes comme le tri par compartiment, qui sont capables d'exploiter la structure des données pour effectuer un tri en une seule passe d'un tableau.

Votre deuxième exemple serait également correct et ressemble à ceci:

O (N ^ 2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

Dans ce cas, pour chaque élément supplémentaire du premier tableau, i, nous devons traiter TOUS j. Ajouter 1 à i ajoute en fait (longueur de j) à j. Vous avez donc raison! Ce modèle est O (n ^ 2), ou dans notre exemple, il s'agit en fait de O (i * j) (ou n ^ 2 si i == j, ce qui est souvent le cas avec des opérations matricielles ou une structure de données carrée.

Votre troisième exemple est celui où les choses changent en fonction des matières premières; Si le code est tel qu'écrit et que do stuff est une constante, ce n'est en fait que O (n) car nous avons 2 passes d'un tableau de taille n, et 2n se réduit à n. Les boucles étant à l'extérieur les unes des autres ne sont pas le facteur clé qui peut produire 2 ^ n code; voici un exemple d'une fonction qui est 2 ^ n:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

Cette fonction est 2 ^ n, car chaque appel à la fonction produit DEUX appels supplémentaires à la fonction (Fibonacci). Chaque fois que nous appelons la fonction, la quantité de travail que nous devons faire double! Cela se développe très rapidement, comme couper la tête d'une hydre et en faire germer deux nouvelles à chaque fois!

Pour votre dernier exemple, si vous utilisez un tri nlgn comme merge-sort, vous avez raison de dire que ce code sera O (nlgn). Cependant, vous pouvez exploiter la structure des données pour développer des tris plus rapides dans des situations spécifiques (par exemple sur une plage de valeurs connue et limitée, comme de 1 à 100). Vous avez cependant raison de penser que le code d'ordre le plus élevé domine; donc si un tri O (nlgn) est à côté de toute opération qui prend moins de temps O (nlgn), la complexité temporelle totale sera O (nlgn).

En JavaScript (au moins dans Firefox), le tri par défaut dans Array.prototype.sort () est en effet MergeSort, donc vous regardez O (nlgn) pour votre scénario final.

Votre deuxième exemple (boucle externe de 0 à n , boucle interne de 0 à b ) serait O ( nb ), pas O ( n ² ). La règle est que vous calculez quelque chose n fois, et pour chacun d'entre vous vous calculez quelque chose d'autre b fois, donc la croissance de cette fonction dépend uniquement de la croissance de n * b .

Votre troisième exemple est juste O ( n ) - vous pouvez supprimer toutes les constantes car elles ne croissent pas avec n et la croissance est ce qu'est la notation Big-O.

Quant à votre dernier exemple, oui, votre notation Big-O proviendra certainement de la méthode de tri qui sera, si elle est basée sur la comparaison (comme c'est généralement le cas), sous sa forme la plus efficace, O ( n * logn ) .

Rappelez-vous qu'il s'agit d'une représentation approximative de l'exécution. La "règle empirique" est approximative parce qu'elle est imprécise mais donne une bonne approximation de premier ordre à des fins d'évaluation.

Le temps d'exécution réel dépendra de la quantité d'espace de stockage, de la vitesse du processeur, du jeu d'instructions, de l'utilisation des préfixes ou des opérateurs d'incrémentation post-fix, etc., yadda. Une analyse d'exécution correcte permettra de déterminer l'acceptation, mais la connaissance des bases vous permet de programmer dès le début.

Je suis d'accord que vous êtes sur la bonne voie pour comprendre comment Big-O est rationalisé d'un manuel à une application pratique. C'est peut-être l'obstacle difficile à surmonter.

Le taux de croissance asymptotique devient important sur de grands ensembles de données et de grands programmes, donc pour des exemples typiques, vous démontrez qu'il n'est pas aussi important pour une syntaxe et une logique appropriées.

Big oh, par définition signifie: pour une fonction f (t) il existe une fonction c * g (t) où c est une constante arbitraire telle que f (t) <= c * g (t) pour t> n où n est une constante arbitraire, alors f (t) existe dans O (g (t)). Il s'agit d'une notation mathématique utilisée en informatique pour analyser les algorithmes. Si vous êtes confus, je recommanderais d'examiner les relations de fermeture, de cette façon, vous pouvez voir dans une vue plus détaillée comment ces algorithmes obtiennent ces valeurs big-oh.

Quelques conséquences de cette définition: O (n) est en fait congru à O (2n).

Il existe également de nombreux types d'algorithmes de tri. La valeur Big-Oh minimale pour un tri de comparaison est O (nlogn), mais il existe de nombreux types avec un Big-Oh pire. Par exemple, le tri de sélection a O (n ^ 2). Certains types sans comparaison peuvent avoir de meilleures valeurs big-oh. Un tri par compartiment a, par exemple, O (n).