Semana 2 - astalberto/AnalisisDeAlgoritmo GitHub Wiki

Eficiencia de algoritmos

Lo que importa no es solo que el algoritmo funcione, sino qué tan rápido y qué tantos recursos usa. Para eso usamos la notación O grande:

O(1): súper rápido, no importa el tamaño de la entrada

O(n): crece lineal con la entrada

O(n2): ya se empieza a poner pesado con datos grandes

O(logn): muy eficiente (como en búsqueda binaria)

O(nlogn): típico de buenos algoritmos de ordenamiento (merge, quick)

O(n!): imprácticos si n crece (evitar)

Se analiza el peor caso, aunque también se puede utilizar el mejor y el promedio.

Caso medio

No siempre se da el peor caso. A veces el algoritmo se comporta mejor en promedio. El caso medio es básicamente “¿cuánto tarda en una entrada cualquiera?”, asumiendo que todas son igual de probables. Ej: búsqueda lineal

En la práctica sirve para comparar algoritmos que son malos en el peor caso pero buenos en promedio.

Cada paso es proporcional al tamaño del subarreglo: O(n) , con n=r−p+1