Grand O nombre d'opérations

Question

Comment calculer le nombre d'opérations que chaque ligne de code prendrait.

Exemple.

Algorithm find2D (A,x) 
    arrLength = A.length 
    for j <- 1 to arrLength – 1 do 
     for k <- 1 to arrLength – 1 do 
       if A[j][k] = x then 
        return true 
      increment k 
    increment j 
return false 

J'ai trouvé ce pseudo-code. Donc, je ne suis pas vraiment sûr de savoir comment compter le nombre d'opérations que chaque ligne de code prend. Donc, comme la première boucle serait 1 + n opérations puisque vous devez définir le j, comparez j à arrLength - 1, et il boucle n-1 fois. Donc cela vous donne n-1 + 1 + 1 qui est n + 1 opérations. Donc, pour la deuxième boucle, ce serait la même chose, même si elle est imbriquée.

Je suis un peu confus sur la comparaison A[j][k] = x, combien d'opérations serait-ce.

Merci.

Answer 1

Big-Oh est asymptotique, vous ne devriez donc pas vous préoccuper du "1" dans "1 + n". Si tout ce que vous cherchez est la classification Big-Oh de ce code, considérez simplement que vous avez deux boucles, l'une imbriquée dans l'autre, et chaque boucle fait un nombre constant d'opérations par élément. Alors la boucle intérieure est O (n), et la boucle extérieure exécute la boucle interne n fois, donc la boucle extérieure est O (n^2). Alors toute la fonction est O (c + n^2) où c est le nombre constant d'opérations du code entourant la boucle extérieure. Puisque Big-Oh est asymptotique, le c disparaît et votre fonction est O (n^2).

Si vous essayez de calculer le nombre exact d'opérations que le code prend, vous devrez probablement établir ce que vous utilisez abstract machine.

Espérons que cela aide.

Answer 2

La règle générale est la suivante:

Pour chaque fois une boucle sur chaque élément d'un tableau, multiplier par N

Pour chaque fois que l'on divise la matrice en deux à plusieurs reprises, il faut multiplier par log (N)

Puisque vous avez deux boucles imbriquées sur l'ensemble du tableau, vous êtes O (N^2).

Le calcul du facteur constant est plus complexe et dépend des détails du langage, du compilateur et du matériel. Fondamentalement, il suffit de travailler empiriquement.

Answer 3

En termes de gros O, vous devez choisir l'opération que vous comptez, la plus fréquente et la plus atomique. Dans ce cas, c'est la comparaison à l'intérieur des deux boucles. Vous n'avez pas besoin de compter combien de boucles de comparaisons font pour itérer, vous devez simplement compter combien de fois la partie la plus interne sera exécutée dans le pire des cas. Ce sera n-1 pour la boucle externe, chacun de n-1 pour la boucle interne, qui donne O(n^2) total.