La complejidad del tiempo en el peor de los casos de Bubble sort es n al cuadrado. Otros algoritmos de ordenación, como la ordenación por fusión, tienen una complejidad de tiempo de n veces log (n) (la base del registro es 2 por cierto si no lo sabe)
Entonces sí. La ordenación de burbujas es más lenta que la fusión u otros algoritmos de ordenación ‘n logn’. En el análisis asintótico, se consideran entradas muy grandes porque la mayoría de las veces tenemos que tratar con ellas, por lo que el algoritmo debería ser bueno cuando se trata de entradas grandes. En la ordenación, las entradas grandes significan tener grandes matrices para ordenar (n es el número de elementos en la matriz).
Para valores pequeños de n burbuja y fusión muestran una diferencia insignificante en su tiempo para completar la ejecución. Pero n cuadrado crece más rápido que nlogn a medida que ‘n’ crece (que es solo otra forma de decir que n crece más rápido que logn). Vamos a verlo con números reales.
- Me acabo de unir a TopCoder porque quiero aprender las estructuras de datos y cómo codificarlas en C, pero no tengo idea de dónde comenzar en TopCoder ya que puedo ver 3 categorías en el sitio, pero no pude encontrar la forma correcta. ¿Qué debo hacer para comenzar?
- ¿Es el tiempo lineal?
- Cómo mantener una matriz, admitir inserción y asignación aleatorias, y consultar el kth elemento más grande en un intervalo dado
- ¿Cuál es la diferencia entre una matriz y una variable?
- ¿Cuál es la solución a la siguiente relación de recurrencia: [matemáticas] T (n) = 3T (n-1) - 7T (n-2) + 9T (n-3) [/ matemáticas], con las siguientes condiciones iniciales: [ matemática] T (0) = 1 [/ matemática], [matemática] T (1) = 6 [/ matemática], [matemática] T (2) = 7 [/ matemática]. ¿Qué es una expresión para [math] T (n) [/ math] de modo que no haya términos [math] T (i (\ frac {n} {j}) ^ {k}) [/ math] a la derecha ¿lado?
n = 2 – Burbuja: 4 Fusionar: 2
n = 4 – Burbuja: 16 Fusionar: 8
n = 8 – Burbuja: 64 Fusionar: 24
n = 16 – Burbuja: 256 Fusionar: 64
n = 64 – Burbuja: 4096 Fusionar: 384
Vea, cómo la burbuja crece más rápido con entradas crecientes que fusionadas. Si el tamaño de su matriz es 64, la ordenación de burbujas toma 10 veces más tiempo que la fusión. Eso significa que si la fusión clasifica 64 elementos en 1 segundo, la burbuja tardaría 10 segundos, lo que es una gran sobrecarga para un algoritmo que no ofrece una ventaja especial sobre otros algoritmos.
Esta diferencia de tiempo se vuelve cada vez más significativa a medida que aumenta el valor de entrada de ‘n’. Muchos programas cotidianos necesitan este aumento y, por lo tanto, la clasificación de burbujas no es muy práctica. La ordenación por fusión, la ordenación rápida y la ordenación en montón son algunos métodos de nlogn y se ha demostrado matemáticamente que ningún algoritmo puede tener una mejor complejidad temporal que nlogn.
Espero que esto ayude.
