O número grande de operaciones

Question

¿Cómo se puede calcular el número de operaciones de cada línea de código tomaría.

Ejemplo.

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

Se me ocurrió con esta pseudo código. Así que no estoy muy seguro de cómo contar el número de operaciones de cada línea de código toma.

Así como el primer bucle sería 1 + n operaciones ya que se debe establecer el j, j comparar a arrLength - 1, y se hará en bucle n-1 veces. Así que le da n-1 + 1 + 1, que es N + 1 operaciones.

Así que para el segundo bucle sería sólo lo mismo a pesar de que su anidada.

Estoy un poco confundido en la comparación A[j][k] = x, el número de operaciones que podría ser.

Gracias.

Answer 1

Big-Oh es asintótica, por lo que no debe preocuparse por el "1" en "1 + n".

Si todo lo que está buscando es la clasificación Big-Oh de ese código, basta con considerar que tiene dos bucles, uno anidado dentro del otro, y cada bucle tiene un número constante de operaciones por elemento. A continuación, el bucle interior es O (n), y el bucle exterior se está ejecutando el bucle dentro de n veces, por lo que el bucle exterior es O (n ^ 2). Entonces toda la función es O (c + n ^ 2) donde c es el número constante de operaciones a partir del código que rodea al bucle exterior. Desde Big-Oh es asintótica, la c desaparece y su función es O (n ^ 2).

Si usted está tratando de calcular el número exacto de las operaciones del código toma, es probable que establecer qué máquina abstracta que está utilizando.

Espero que esto ayude.

Answer 2

La regla general es la siguiente:

Para cada vez que un bucle sobre cada elemento de una matriz, se multiplica por N

Para cada vez que se divide la matriz en dos repetidamente, se multiplica por log (N)

Dado que usted tiene dos bucles anidados sobre toda la matriz, usted es O (N ^ 2).

El cálculo del factor constante es más difícil, y depende de los detalles de la lengua, compilador, y el hardware. Básicamente sólo hay que trabajar en eso empíricamente.

Answer 3

En cuanto a la gran O, usted debe elegir la operación que va a contar, más frecuente y uno atómica. En este caso se trata de la comparación dentro de los dos bucles. No es necesario contar cuántas comparaciones bucles están haciendo para iterar, que acaba de contar cuántas veces la parte más interna se ejecutará en el peor de los casos. Será n-1 para bucle exterior, cada uno de n-1 para el bucle interior, que da total de O(n^2).