algorithm - resueltos - ¿Por qué la complejidad Big-O de este algoritmo O(n ^ 2)?

complejidad en el tiempo

Question

Sé que la complejidad big-O de este algoritmo es O(n^2) , pero no puedo entender por qué.

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

Aunque establezcamos j = n * n al principio, incrementamos i y disminuimos j durante cada iteración, entonces, ¿no debería ser el número resultante de iteraciones mucho menor que n*n ?

Answer 1

Aunque establezcamos j = n * n al principio, incrementamos i y disminuimos j durante cada iteración, entonces, ¿no debería ser el número resultante de iteraciones mucho menor que n * n?

¡Si! Por eso es O (n ^ 2). Por la misma lógica, es mucho menor que n * n * n , lo que lo convierte en O (n ^ 3). Incluso es O (6 ^ n), por lógica similar.

big-O le brinda información sobre los límites superiores.

Creo que está tratando de preguntarse por qué la complejidad es theta (n) u omega (n), pero si solo está tratando de entender qué es Big-O, realmente necesita comprender que primero da límites superiores a las funciones y principal.

Answer 2

Durante cada iteración, usted incrementa i disminuye j que equivale a simplemente incrementar i en 2. Por lo tanto, el número total de iteraciones es n ^ 2/2 y eso sigue siendo O (n ^ 2).

Answer 3

La complejidad big-O ignora los coeficientes. Por ejemplo: O(n) , O(2n) y O(1000n) son todos el mismo tiempo de ejecución de O(n) . Del mismo modo, O(n^2) y O(0.5n^2) son ambos O(n^2) tiempo de ejecución.

En su situación, esencialmente está incrementando su contador de bucle en 2 cada vez a través de su bucle (ya que j-- tiene el mismo efecto que i++ ). Entonces, su tiempo de ejecución es O(0.5n^2) , pero eso es lo mismo que O(n^2) cuando elimina el coeficiente.

Answer 4

Sí, este algoritmo es O (n ^ 2).

Para calcular la complejidad, tenemos una tabla de las complejidades:

O (1) O (log n) O (n) O (n log n)
O (n²) O (n ^ a) O (a ^ n) O (n!)

Cada fila representa un conjunto de algoritmos. Un conjunto de algoritmos que está en O (1), también está en O (n) y O (n ^ 2), etc. Pero no a la inversa. Entonces, su algoritmo realiza n * n / 2 oraciones.

O (n) <O (nlogn) <O (n * n / 2) <O (n²)

Entonces, el conjunto de algoritmos que incluyen la complejidad de su algoritmo es O (n²), porque O (n) y O (nlogn) son más pequeños.

Por ejemplo: Para n = 100, suma = 5000. => 100 O (n) <200 O (n · logn) <5000 (n * n / 2) <10000 (n ^ 2)

Lo siento por mi Inglés.

Answer 5

Sea m el número de iteraciones tomadas. Entonces,

i + m = n ^ 2 - m

lo que da,

m = (n ^ 2-i) / 2

En la notación Big-O, esto implica una complejidad de O (n ^ 2).

Answer 6

Su algoritmo es equivalente a

while (i += 2 < n*n) 
  ...

que es O(n^2/2) que es igual a O(n^2) porque a la gran complejidad de O no le importan las constantes.

Answer 7

Tendrá exactamente n*n/2 iteraciones de bucle (o (n*n-1)/2 si n es impar). En la notación O grande tenemos O((n*n-1)/2) = O(n*n/2) = O(n*n) porque los factores constantes "no cuentan".