¿Se puede ordenar una lista de números en un número menor de pases que el indicado por la notación Big-O?

Hay algunas ideas erróneas con respecto a la notación O grande y lo que realmente significa que un algoritmo tiene complejidad O (f (n)).

En primer lugar, la notación no tiene en cuenta factores como el almacenamiento en caché, el tiempo de acceso a la memoria, etc.

Además, no dice con precisión cuánto tiempo llevará completar un algoritmo; solo proporciona un límite superior como relación. Eso significa que para bubbleort, duplicar el tamaño de entrada cuadruplicará (en lugar de duplicar) el tiempo de ejecución.

Finalmente, el límite superior solo puede contener (arbitrariamente) grandes tamaños de entrada.

Entonces, en total, en una computadora real , para un tamaño de entrada pequeño, la respuesta es sí, es completamente posible que un algoritmo pueda tener un tiempo de ejecución que “viole” la notación O grande.

SÍ, puede tener un tiempo de ejecución más rápido de lo que dicta la notación big-O. Big-O es un límite superior asintótico, que significa para entradas GRANDES, que es aproximadamente qué tan rápido, a lo sumo, el algoritmo se ejecuta hasta un multiplicador constante y una suma de términos más pequeños de crecimiento más lento. (EG, [matemáticas] .5 N ^ 2 + N – log (N) = O (N ^ 2) = O (N ^ 3) [/ matemáticas])

¡Espera, hay más! Hay algo llamado big-theta, que establece un asintótico EXACTO unido a una constante. Entonces, incluso entonces, si la función se ejecuta en [matemática] .5 N [/ matemática], es decir [matemática] \ Theta (N) [/ matemática] asintóticamente. ¡Dado eso, se ejecutaría en la mitad del tiempo de lo que diría la notación big-theta (o, incluso, qué big-O) diría!

La notación es una indicación del peor caso posible. En un algoritmo O (N), en el peor de los casos, tendrás que hacer algo N veces. En el mejor de los casos, es posible que solo tenga que hacer la cosa una vez, pero eso * no * significa que el algoritmo es O (1) en general. Sin embargo, un tipo de burbuja no optimizado siempre será O (N ^ 2) por naturaleza de los bucles utilizados:

para (0 para (0 hacer algo con la colección

Debería ser obvio que “hacer algo con la colección” se ejecuta N ^ 2 veces.

Mucha más información sobre el tipo de burbuja.

La notación Big-O es una forma de describir hechos. No impone ningún límite en sí mismo.

La notación Big-O describe un límite superior a medida que crece el número de . Cualquier función que sea O (n) también es O (n ^ 2), aunque si la describe así a las personas, pensarán que está equivocado y le preguntarán por qué no acaba de decir O (n).

Para la ordenación de burbujas en particular, puede comenzar con elementos que están ordenados (por suerte) y poder decir que todos están ordenados en una sola pasada. Eso significa que esto es O (n) para datos ya ordenados. Para el peor de los casos, estás haciendo mucho más comparación / intercambio que eso.

Para los algoritmos en general, puede haber un O () diferente para el peor de los casos, el mejor de los casos, el caso típico, etc. No tiene que haber un solo O () para todo el algoritmo. También puede especificar la complejidad en términos de tiempo o espacio.

Por definición, no puede ser más rápido que el mejor de los casos.

A Dijkstra se le ocurrió un algoritmo de clasificación que tiene una complejidad más cercana a la lineal si la lista está más cerca de ser ordenada.

Smoothsort

PD: la notación big-oh solo dicta el comportamiento hasta una constante. Por lo tanto, no puede razonar a partir de un solo ejemplo.

• La notación O grande es solo una notación para el comportamiento asintótico de una función, no “declara” nada sobre listas de números de clasificación de burbujas bubble
• Big O es un límite superior, por lo que si dice “bubbleort utiliza O (2 ^ n) pasa sobre la matriz”, entonces eso es cierto a pesar de que también es O (n). Y si usted dice, “el tipo de burbuja tiene O (n) pasa”, eso también es cierto incluso si para algunas entradas es menor que eso.