Grand nombre O des opérations

Question

Comment calculer le nombre d'opérations 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

Je suis venu avec ce code pseudo. Je ne suis pas vraiment sûr de la façon de compter le nombre d'opérations chaque ligne de code prend.

Alors que la première boucle serait 1 + n opérations puisque vous devez définir le j, j comparer à arrLength - 1, et en boucle n-1 fois. Cela vous donne n-1 + 1 + 1 qui est n + 1 opérations.

Donc, pour la deuxième boucle serait-il juste la même chose, même si son emboîtée.

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

Merci.

Answer 1

Big-Oh est asymptotique, vous ne devriez pas être concerné par le "1" dans "1 + n".

Si tout ce que vous cherchez est la classification Big-Oh de ce code, il suffit de considérer 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. Ensuite, la boucle de l'intérieur est en O (n), et la boucle extérieure est en cours d'exécution à l'intérieur de la boucle de n fois, de sorte que la boucle externe est O (n ^ 2). Ensuite, la fonction entière est O (C + N ^ 2), où c est le nombre constant d'opérations à partir du code qui entoure la boucle extérieure. Depuis Big-Oh est asymptotique, c disparaît et votre fonction est O (n ^ 2).

Si vous essayez de calculer le nombre exact d'opérations prend le code, vous aurez probablement besoin d'établir ce que

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

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

Puisque vous avez deux boucles imbriquées sur tout le tableau, vous êtes O (N ^ 2).

Calcul du facteur de constante est plus délicate, et dépend des détails de la langue, le compilateur et le matériel. Fondamentalement, ont juste besoin de travailler que de façon empirique.

En termes de grand O, vous devez choisir l'opération que vous allez compter, plus un fréquent et atomique. Dans ce cas, il est la comparaison dans les deux boucles. Vous n'avez pas besoin de compter combien de boucles comparaisons font pour itérer, vous comptez combien de fois la partie la plus interne sera exécutée dans le pire des cas. Il sera n-1 pour boucle extérieure, chacune n-1 boucle intérieure, qui donne un total de O(n^2).

Answer 3

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

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

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

Puisque vous avez deux boucles imbriquées sur tout le tableau, vous êtes O (N ^ 2).

Calcul du facteur de constante est plus délicate, et dépend des détails de la langue, le compilateur et le matériel. Fondamentalement, ont juste besoin de travailler que de façon empirique.

Answer 4

En termes de grand O, vous devez choisir l'opération que vous allez compter, plus un fréquent et atomique. Dans ce cas, il est la comparaison dans les deux boucles. Vous n'avez pas besoin de compter combien de boucles comparaisons font pour itérer, vous comptez combien de fois la partie la plus interne sera exécutée dans le pire des cas. Il sera n-1 pour boucle extérieure, chacune n-1 boucle intérieure, qui donne un total de O(n^2).