¿Qué es la complejidad del tiempo Big O?

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

La notación O grande expresa a qué ritmo aumenta la cantidad de cálculo a medida que aumenta el tamaño de entrada. El propósito es diferente de un punto de referencia que dice exactamente cuántos nanosegundos se necesitan.

Complejidad vista con frecuencia

Acceso al índice de matriz O (1)
Búsqueda binaria O (log N)
O (N) recorrido completo
O (N log N) clasificación de comparación general
O(N²) compara todos los pares

Se omiten las constantes

for (int Value : Values)
{
    ProcessA(Value);
}

for (int Value : Values)
{
    ProcessB(Value);
}

Dado que se recorre dos veces, la operación real es2NCerca, pero en Big OO(N)expresarlo como Esto se debe a que se centra en el orden creciente a medida que N crece.

Ignorar las constantes no significa que no sean importantes en el desempeño real. compatible con cachéO(N)Si su código es diferente con constantes complejasO(N)Puede ser mucho más rápido que el código.

peor, promedio, mejor

La búsqueda lineal encuentra el primer elemento.O(1), pero si falta o está al finalO(N)soy. Si no anotas de qué caso estás hablando, el mismo algoritmo se explicará de forma diferente.

Big O es el primer filtro para elegir un algoritmo. La elección final debe sopesarse en función del tamaño real de los datos, el uso de la memoria, el caché y la complejidad de la implementación.