Las anotaciones BigO (en la teoría de la informática) permiten clasificar para un conjunto dado de entradas, qué orden de magnitud tomaría el algoritmo en tiempo de ejecución (y / o espacio-tiempo). Permite tomar las mejores decisiones para elegir un algoritmo dado para un problema en particular o conocer sus limitaciones de antemano.
Considere los ejemplos triviales de varios algoritmos de clasificación y búsqueda, la notación BigO permitiría describir por qué la clasificación por fusión puede ser mejor o peor que la clasificación rápida y / o mejor o peor que la clasificación por burbujas.
Como usuario de algoritmos de búsqueda, por ejemplo, lo ideal sería utilizar una estructura de datos que se ejecute en O (1) (por ejemplo, tabla hash o tabla de búsqueda). ¿O es aceptable que el tiempo de ejecución sea O (log n), que es aplicable en una búsqueda de árbol binario ordenado. O para ordenar ejemplos, habrá restricciones de memoria o restricciones de tiempo de ejecución o ambas. Si mi tamaño de entrada es menor y mis requisitos de memoria son menores, ¿sería aceptable elegir un tipo de ejecución lenta?
- ¿Cuál es la estrategia de divide y vencerás? Escribe un algoritmo para encontrar x a la enésima potencia usando el método de dividir y conquistar.
- ¿Nuestro código genético utiliza algoritmos de compresión?
- Cómo encontrar el número máximo de árboles de expansión mínima en un gráfico
- ¿Cuál es el algoritmo de clasificación menos eficiente?
- ¿Cuál: Estructura de datos y pensamiento algorítmico con Python (Narasimha Karumanchi) o Estructuras de datos y algoritmos en Python (Michael T. Goodrich)?
Como parte del análisis y diseño de algoritmos en Ciencias de la Computación, tenemos que entender cuál es la complejidad de cada algoritmo en términos de notación Big O (o cómo llegar a la notación Big O en primer lugar para un algoritmo dado). Luego, realiza compensaciones analizando varios algoritmos para una solución particular de un problema.
Espero que esto te de algunas ideas.
