¿Por qué es importante considerar las anotaciones asintóticas (como límite superior, límite inferior y límite estrecho)?

Los límites son importantes porque te dan una idea de qué tan bien se escala tu algoritmo. Suponga que escribe este fragmento de código para hacer una tarea simple razonablemente bien; por ejemplo, ordene un conjunto de números usando el ordenamiento de burbujas. Escribes código, ingresas una matriz de miles de números en orden inverso y descubres el tiempo que lleva hacerlo. Supongamos que tarda 10 milisegundos (eso es una centésima de segundo) en completarse. Lo cual, sientes que es bastante bueno.

Ahora, decide usarlo para matrices más grandes, como una matriz que consta de mil millones de números. Probablemente razone, si se necesitan 10 milisegundos para ordenar 1000 números, se necesitan 10,000 segundos para ordenar mil millones de números, ¿verdad? Eso es menos de 3 horas y se ve bien para un trabajo cron durante la noche.

Aquí es donde entran los límites en la imagen. El peor rendimiento para el ordenamiento de burbujas es [matemática] O (n ^ 2) [/ matemática]. Lo que significa que el tiempo máximo que puede tomar es proporcional no al tamaño de su entrada, sino al cuadrado del tamaño de su entrada. El cálculo es así:

[matemáticas] (10 ^ 3) ^ 2 \ a 10 [/ matemáticas] milisegundos

[matemática] 10 ^ 9 \ a 10 [/ matemática] milisegundos

[matemáticas] 1 \ a 10 ^ {- 8} [/ matemáticas] milisegundos

[matemáticas] (10 ^ 9) ^ 2 = 10 ^ {18} \ a 10 ^ {10} [/ matemáticas] milisegundos

Eso es más de 2777 horas de tiempo de clasificación para usted. Lo que podría haber evitado si hubiera tenido en cuenta los límites de su algoritmo de elección.

Proporcionan una tendencia básica de cómo los algoritmos se escalan para conjuntos de datos muy grandes.

La notación asintótica no siempre es importante de considerar, ya sea porque nuestro algoritmo está garantizado para operar en un tamaño de entrada suficientemente pequeño que generalmente funciona bien independientemente de la elección del algoritmo, o porque el comportamiento asintótico por sí solo no es suficiente para el propósito de la aplicación. Ese es el caso cuando se crean aplicaciones de tiempo crítico, sistemas en tiempo real, etc. Cuando se necesita optimizar tanto como sea posible, las abstracciones pueden ser inadecuadas. Es posible que deba expandir la función de tiempo de ejecución en su forma completa, teniendo en cuenta las constantes, los factores de orden inferior y los parámetros dependientes de la máquina. La notación asintótica no da mucha importancia; solo buscamos la tendencia general.

Ahora, la razón por la que nos permitimos el descuido de las estimaciones aproximadas es que, aunque los ciclos de CPU y la potencia de procesamiento tienden a mejorar con el tiempo, existen límites físicos reales para la tecnología involucrada. En algún momento, los científicos informáticos descubrieron que el verdadero obstáculo del rendimiento estaba cambiando del hardware a las características intrínsecas de los algoritmos mismos que dictan su capacidad para funcionar en tamaños de entrada perpetuamente más grandes, aumentando así la potencia de procesamiento de los sistemas informáticos más allá de sus limitaciones de hardware .

En esa dirección, trabajamos bajo el supuesto de que las constantes y el factor de orden inferior son intrascendentes. La predicción del tiempo de ejecución no tiene que ser exacta en el caso general. Según la definición de Big-Oh, si el tiempo de ejecución está limitado por tiempos constantes de otra función, todo lo que tenemos que hacer en el peor de los casos es agregar suficientes procesadores y tenemos la garantía de que el algoritmo funcionará como se pronostica asintóticamente.

En resumen, lo que hace la notación asintótica para nosotros es que simplifica y mejora nuestro poder predictivo sobre el rendimiento de los algoritmos a largo plazo. A medida que los datos crecen y la demanda de procesamiento aumenta, la relevancia de los buenos algoritmos se vuelve más clara, ya que nos permiten superar las limitaciones físicas de nuestros sistemas.

Debido a que se utilizan en casi todas las ciencias basadas en la tecnología que requieren una visión general rápida del problema, observando cuán complicado, fácil de optimizar, rápido o lento (cuando se describe un proceso) como función es.

Esto abarca desde el mercado de valores, pasando por la tecnología de la información hasta la ingeniería dura, como el diseño de controladores de procesos industriales.
Ningún ingeniero serio en estos días puede diseñar nada sin conocer los conceptos básicos de la notación Bachmann-Landau.