El objetivo de la notación Big-O es describir cómo el espacio y el tiempo necesarios para ejecutar un algoritmo varía con el tamaño de entrada variable. La otra persona ya te ha dado la definición matemática. Entonces te daré una intuitiva. Le dan una idea sobre cómo se escala el algoritmo.
Consideremos un caso simple. Comparación de inserción y clasificación de fusión para entradas grandes. Sus complejidades temporales se describen como [matemáticas] O (N ^ 2) [/ matemáticas] y [matemáticas] O (N \ log N) [/ matemáticas] respectivamente. ¿Qué quieren decir?
Considere ordenar una matriz de [matemáticas] 10 ^ 6 [/ matemáticas] (un millón) enteros. (Ignore las constantes por un momento. Lo consideraré más adelante). Ahora, en el peor de los casos, necesita alrededor de [matemáticas] 10 ^ {12} [/ matemáticas] operaciones en caso de fusión, sería alrededor de [matemáticas] 2 \ multiplicado por 10 ^ 7 [/ math] operaciones.
- Cómo escribir un programa para implementar la búsqueda binaria
- ¿Cuáles son los mejores libros para algoritmos y estructuras de datos en C?
- ¿La programación lineal admite un algoritmo de tiempo fuertemente polinómico?
- ¿Existe un algoritmo que pueda combinar y separar números?
- Cómo declarar un conjunto de cadenas de tamaño desconocido para obtenerlo del usuario sin usar la función de asignación en C
Aumentemos el tamaño de la entrada y luego ejecutemos los algoritmos en ellos. Aumentemos el tamaño de la entrada en 10 veces. La ordenación por inserción necesita operaciones [matemática] 10 ^ {14} [/ matemática] y la fusión necesita alrededor de [matemática] 2.4 \ veces 10 ^ 8 [/ matemática] operaciones.
El número de operaciones necesarias aumentó alrededor de 12 veces en caso de una fusión. En caso de inserción, es alrededor de 100 veces. (Nota: Esto puede no ser exacto ya que depende de muchos factores. Pero el orden de cambio sigue siendo el mismo).
Esto es lo que te dice la notación Big-O. Así es como puede obtener una idea aproximada sobre cómo el algoritmo se escala al aumentar el tamaño de entrada. Pero eso no es todo. En muchas implementaciones de bibliotecas, las matrices pequeñas se ordenan por orden de inserción. ¿Por qué? Aquí es donde las constantes se vuelven importantes. Por lo tanto, una menor complejidad asintótica no significa necesariamente que el tiempo de ejecución sea mejor. En otras palabras, citando la respuesta de Paul Tardy, si [math] n_0 [/ math] es demasiado grande para ser práctico, probablemente sería mejor con el de mayor complejidad si es práctico.
