Significado y funcionamiento
El ordenamiento es el proceso de reorganizar datos de acuerdo con un orden específico. El algoritmo de "bubble sort" compara elementos adyacentes, y el algoritmo de "merge sort" utiliza una estructura que combina listas divididas.
La estructura iterativa de un algoritmo determina cuánto aumenta la carga de trabajo a medida que aumenta el tamaño de la entrada. Incluso con el mismo tamaño, el orden inicial y las condiciones de terminación de la implementación pueden alterar los resultados.
Relaciones y condiciones de validez
La escala comparativa para un algoritmo de bubble sort típico es O(n²), mientras que merge sort tiene una escala de O(n log n). Es importante destacar que un número específico de comparaciones y la notación asintótica O no son lo mismo.
El experimento no es una medida que cuenta el número de comparaciones de valores, intercambios y escrituras para determinar el tiempo real de un ordenador. No considera las escrituras de datos y los intercambios de posición como la misma operación.
Qué observar en la simulación
Las comparaciones dependen del tamaño, orden inicial y algoritmo.
Contamos comparaciones e intercambios. Las escrituras de mezcla se cuentan aparte.
Relaciones y símbolos clave
bubble: n(n−1)/2 · merge: O(n log₂n)
| Símbolo | Significado | Unidad |
|---|---|---|
| n | Número de datos de entrada | unidades |
| O(n log n) | Expresión superior para la representación del crecimiento asintótico según el tamaño de la entrada. | Complejidad |
Ejemplo resuelto
¿Escribir y intercambiar son la misma operación?
Son distintas · Las comparaciones dependen del tamaño, orden inicial y algoritmo.
Errores frecuentes
- El hecho de que el número de comparaciones sea pequeño no significa que todos los ordenadores e entradas se acortarán en la misma proporción en términos de tiempo.