Tricky Big-O complejidad

Question

public void foo(int n, int m) { 
    int i = m; 

    while (i > 100) { 
     i = i/3; 
    } 
    for (int k = i ; k >= 0; k--) { 
     for (int j = 1; j < n; j *= 2) { 
      System.out.print(k + "\t" + j); 
     } 
     System.out.println(); 
    } 
} 

Me imaginé que la complejidad sería O (logn).
Eso es como un producto del bucle interno, el bucle externo - nunca se ejecutará más de 100 veces, por lo que se puede omitir.

lo que no estoy seguro es de la cláusula, mientras que, si se incorpora a la complejidad de Big-O? Para valores muy grandes i que podría tener un impacto, o operaciones aritméticas, no importa en qué escala, cuente como operaciones básicas y se puede omitir?

Answer 1

El bucle while es O(log m) porque continúan dividiéndose m por 3 hasta que sea inferior o igual a 100.

Desde 100 es una constante en su caso, puede ser ignorada, sí.

El bucle interior es O(log n) como ha dicho, porque se multiplica j por 2 hasta que excede n.

Por lo tanto la complejidad total es de O(log n + log m).

operaciones aritméticas, no importa a qué escala, cuente como operaciones básicas y se puede omitir?

Las operaciones aritméticas por lo general se pueden omitir, sí. Sin embargo, también depende del idioma. Parece Java y parece que estás usando tipos primitivos. En este caso, está bien considerar las operaciones aritméticas O(1), sí. Pero si usa números enteros grandes, por ejemplo, eso ya no está bien, ya que la suma y la multiplicación ya no son O(1).

Answer 2

La complejidad es O (log m + log n).

El bucle while ejecuta LOG3 (m) veces - una constante (log3 (100)). El bucle for externo se ejecuta una cantidad constante de veces (alrededor de 100), y el bucle interno ejecuta log2 (n) veces.

Answer 3

El bucle while divide el valor de m en un factor de 3, por lo tanto el número de tales operaciones será log (base 3) m

Para el para bucles usted podría pensar en el número de operaciones como 2 sumatorias -

suma (k = 0 a i) [suma (j = 0 a lg n) (1)] suma (k = 0 a i) [lg n + 1] (lg n + 1) (i + 1) será el número total de operaciones, de las cuales domina el término de registro.

Es por eso que la complejidad es O (log (BASE 3) m + lg n) Aquí el LG se refiere a conectarse a la base 2