Los más significativos son O, theta y omega. O a veces se llama el peor de los casos, omega a veces se llama el mejor de los casos, y theta es el peor de los casos y el mejor de los casos, y existe solo si O es lo mismo que omega.
Además, la notación describe cómo un algoritmo escala con los parámetros de entrada. Por ejemplo, O (1) significa que el peor de los casos es constante, O (n) significa que el peor de los casos se escala con n, lo que significa que para el doble de los parámetros generalmente se duplica el tiempo de ejecución. Para O (n ^ 2) los parámetros dobles le darían un tiempo de ejecución cuádruple y así sucesivamente.
Ejemplos: la búsqueda de matriz lineal tiene O (n) y omega (1). El peor de los casos es si el elemento que estás buscando es el último que miras, y el mejor de los casos es si el elemento que estás buscando es el primer elemento que miras. Theta no existe.
- ¿Qué son los algoritmos y la estructura de datos y cómo puedo comenzar con ellos?
- Cuando se ejecuta el ordenamiento rápido aleatorio, ¿cuántas llamadas se realizan al generador de números aleatorios en el peor de los casos? ¿Y también para el mejor caso?
- ¿Cuál sería un algoritmo para aplicar un filtro rosa a una imagen?
- ¿Los estudiantes de pregrado de CS estadounidenses entienden todas las matemáticas en sus libros de texto conceptualmente?
- ¿Qué es el desplazamiento binario y por qué lo usamos?
Para el tipo de fusión, tendrá O (n logn), omega (n logn), que a su vez también implica theta (n logn). No importa cómo se vea su entrada, siempre tendrá la misma operación y enfoque para la entrada.
Puede encontrar más ejemplos en Internet, solo busque la complejidad de cualquier algoritmo.
