algorithm - Análisis Big-O para un bucle

loops for-loop

Question

Tengo que analizar este bucle, entre otros, y determinar su tiempo de ejecución utilizando la notación Big-O.

for ( int i = 0; i < n; i += 4 )
    for ( int j = 0; j < n; j++ )
        for ( int k = 1; k < j*j; k *= 2 )`

Esto es lo que tengo hasta ahora:

for ( int i = 0; i < n; i += 4 ) = n

for ( int j = 0; j < n; j++ ) = n

for ( int k = 1; k < j*j; k *= 2 ) = log^2 n

Ahora el problema al que estoy llegando es el tiempo de ejecución final del bucle. Mi mejor conjetura es O (n ^ 2), sin embargo, no estoy seguro de si esto es correcto. ¿Alguien puede ayudar?

Edición: perdón por la cosa Oh -> O. Mi libro de texto usa "Big-Oh"

Answer 1

En primer lugar, tenga en cuenta que el bucle externo es independiente de los dos restantes, simplemente agrega un multiplicador (n/4)* . Lo consideraremos más adelante.

Ahora consideremos la complejidad de

for ( int j = 0; j < n; j++ )
    for ( int k = 1; k < j*j; k *= 2 )

Tenemos la siguiente suma:

0 + log ₂ (1) + log ₂ (2 * 2) + ... + log ₂ (n * n)

Es bueno tener en cuenta que log ₂ (n ^ 2) = 2 * log ₂ (n). Así re-factorizamos la suma para:

2 * (0 + log ₂ (1) + log ₂ (2) + ... + log ₂ (n))

No es muy fácil analizar esta suma, pero eche un vistazo a esta publicación . Usando la aproximación de Sterling, uno puede ser que pertenece a O(n*log(n)) . Por lo tanto, la complejidad global es O((n/4)*2*n*log(n))= O(n^2*log(n))

Answer 2

La complejidad del tiempo de un bucle se considera O (n) si las variables del bucle se incrementan / disminuyen en una cantidad constante (que es c en los ejemplos a continuación):

   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

La complejidad del tiempo de los bucles anidados es igual al número de veces que se ejecuta la instrucción más interna. Por ejemplo, los siguientes bucles de ejemplo tienen una complejidad de tiempo O (n²) :

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

La complejidad del tiempo de un bucle se considera O (logn) si las variables del bucle se dividen / multiplican por una cantidad constante:

for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

Ahora tenemos:

for ( int i = 0; i < n; i += 4 ) <----- runs n times
    for ( int j = 0; j < n; j++ ) <----- for every i again runs n times
        for ( int k = 1; k < j*j; k *= 2 )` <--- now for every j it runs logarithmic times.

Entonces, la complejidad es O (n²logm), donde m es n², que se puede simplificar a O (n²logn) porque n²logm = n²logn² = n² * 2logn ~ n²logn .

Answer 3

• En términos de j , el bucle interno es O(log_2(j^2)) tiempo, pero sine log_2(j^2)=2log(j) , en realidad es O(log(j)) .

• Para cada iteración del bucle medio, toma O (log (j)) tiempo (para hacer el bucle interno), por lo que necesitamos sumar:

  suma {log (j) | j = 1, ..., n-1} log (1) + log (2) + ... + log (n-1) = log ((n-1)!)

Y como log((n-1)!) Está en O((n-1)log(n-1)) = O(nlogn) , podemos concluir que las operaciones de O(nlogn) bucle medio medio.

• Tenga en cuenta que tanto el bucle medio como el interno son independientes de i , por lo tanto, para obtener la complejidad total, podemos multiplicar n/4 (número de repeticiones del bucle externo) con la complejidad del bucle medio, y obtener:

  O (n / 4 * nlogn) = O (n ^ 2logn)

Entonces, la complejidad total de este código es O(n^2 * log(n))