¡También estoy aprendiendo algoritmos!
La notación Big O describe la eficiencia de los algoritmos a medida que aumenta el tamaño de la entrada. Expresa un algoritmo en términos de una función O (n). A medida que aumenta el tamaño de n, el tiempo de ejecución aumenta a una velocidad predecible, que se puede modelar como una función.
En general, hay siete funciones principales (clasificadas de la más rápida a la más lenta):
- Cómo demostrar que O (f (n) - g (n)) no es necesariamente igual a O (f (n)) - O (g (n))
- ¿Qué son los árboles de búsqueda binarios?
- Cómo escribir un programa ruby para mostrar los números de Armstrong en una matriz (siendo la matriz; Números = [123,124,153,370,234,23,45]
- Mientras codifica problemas algorítmicos durante una entrevista usando C, ¿está bien asumir funciones de biblioteca?
- Cómo construir un algoritmo automatizado de comercio de acciones utilizando mis estrategias sin tener que contratar un programador
- O (1): una función constante que siempre se ejecuta en la misma cantidad de tiempo, independientemente del tamaño de la entrada.
- O (logn): una función logarítmica que reduce constantemente el tamaño de entrada en una fracción (generalmente a la mitad como en la búsqueda binaria).
- O (n) – Una función lineal donde el tiempo de ejecución aumenta en proporción al tamaño de la entrada.
- O (nlogn): esta función crece un poco más rápido que la función lineal, pero mucho menos rápido que la función cuadrática. En general, estos algoritmos combinan una operación O (n) con una operación O (logn).
- O (n ^ 2): una función cuadrática en la que el tiempo de ejecución aumenta exponencialmente en un factor de dos a medida que aumenta el tamaño de la entrada. Esta función se encuentra más comúnmente en bucles anidados.
- O (n ^ 3): una función cúbica donde el tiempo de ejecución aumenta exponencialmente en un factor de tres a medida que aumenta el tamaño de la entrada. Un ejemplo simple es un algoritmo que requiere bucles anidados triples.
- O (2 ^ n): una función exponencial en la que el tiempo de ejecución aumenta exponencialmente por un factor de n a medida que aumenta el tamaño de la entrada. ¡Esto es realmente malo! Un ejemplo sería usar la fuerza bruta para descifrar una contraseña generando todas las combinaciones posibles.
Es importante destacar que la notación Big O describe el peor desempeño de un algoritmo. No refleja el rendimiento del algoritmo en cada situación. Por ejemplo, agregar un elemento a una lista dinámica es O (n). En la mayoría de los casos, agregar un elemento a una lista toma O (1) tiempo al asignar el elemento a la siguiente posición no ocupada en la lista. Sin embargo, cuando una lista alcanza su capacidad total, debe cambiar su tamaño creando una nueva lista con una capacidad mayor y copiando sobre cada elemento. Por lo tanto, en el peor de los casos, agregar un elemento es O (n).
La notación Big O también generaliza la eficiencia de los algoritmos. Si un algoritmo tiene un tiempo de ejecución de O (2n), la constante se descarta para producir O (n). Del mismo modo, si un algoritmo tiene un tiempo de ejecución de O (n + logn), el término no dominante se descarta para producir O (n). Esto se debe a que la notación Big O describe la tasa de aumento en el tiempo, no necesariamente qué tan rápido se ejecuta realmente un algoritmo.
Espero que hayas aprendido algo!
