Incluso si dos listas tienen la misma longitud, el tiempo requerido para ordenarlas es diferente. ¿Alguien puede explicar por qué es así?

Answer 1

El tiempo requerido para ordenar varía debido a la diferencia en la disposición del elemento presente en la lista. Debido a la diferente disposición, el mismo algoritmo de clasificación puede tener un orden diferente de complejidades de tiempo.

por ejemplo :

Teniendo en cuenta el algoritmo de clasificación de inserción, puede haber tres casos El mejor caso, el peor caso y el caso promedio dependiendo del orden de la lista de entrada (o simplemente la disposición) .Aunque estos tres casos, es decir, el mejor caso, el peor caso y el caso promedio, existen también para otros algoritmos de clasificación. una matriz que se clasificará mediante ordenación por inserción, entonces puede haber los siguientes tres casos:

Mejor caso :

La mejor entrada de caso es una matriz que ya está ordenada . En este caso, la ordenación por inserción tiene un tiempo de ejecución lineal (es decir, O ( n )). Durante cada iteración, el primer elemento restante de la entrada solo se compara con el elemento más a la derecha de la subsección ordenada de la matriz.

Peor de los casos :

La entrada más simple para el peor de los casos es una matriz ordenada en orden inverso . El conjunto de todas las entradas de caso más desfavorable consiste en todas las matrices donde cada elemento es el más pequeño o el segundo más pequeño de los elementos anteriores. En estos casos, cada iteración del bucle interno escaneará y desplazará toda la subsección ordenada de la matriz antes de insertar el siguiente elemento. Esto le da al tipo de inserción un tiempo de ejecución cuadrático (es decir, O ( n ^ 2)).

Caso promedio:

El caso promedio también es cuadrático, lo que hace que la ordenación por inserción sea poco práctica para clasificar matrices grandes.

Suponga que tiene que ordenar una matriz con 10 ^ 6 elementos. Luego, en el peor de los casos, para una CPU general, que puede procesar 10 ^ 8 operaciones por segundo, tomará aproximadamente 2.77 h mientras que para ordenar la misma (10 ^ 6 elementos) No. de elementos en el mejor de los casos, la misma CPU tomaría menos de un segundo.

Answer 2

Hay varios atributos que cuentan para el rendimiento general de la Clasificación. Los principales pueden resumirse como (muchos otros podrían no estar disponibles aquí):

1. El algoritmo de clasificación : el código o la lógica que elige ordenar.
2. El tamaño de entrada : el tamaño de la entrada para ordenar.
3. La disposición actual de los elementos de entrada : la lista puede estar parcialmente ordenada, completamente ordenada o totalmente desordenada.
4. El hardware : la CPU / RAM / hardware en la que se realiza la clasificación también afecta el rendimiento.

Concluyendo, no solo el tamaño de dos recuentos de listas diferentes, sino también otros parámetros, mientras se ordena (o cualquier otra operación).

¡Sigue aprendiendo, cosa lógica! Saludos 🙂

Answer 3

1. Diferentes entradas pueden resolverse más rápido y más lento por el algoritmo. Uno de su lista es un mejor caso para el algoritmo específico que utiliza que el otro. Al igual que en la vida real, probablemente la analogía más común utilizada para la clasificación es cuando clasifica las cartas en la mano durante un juego (que es un ejemplo bastante pobre para usar, pero funciona aquí), entonces no le resulta sorprendente en absoluto que una vez obtienes una mano que te toma menos tiempo para ordenar y la otra vez la que lleva más tiempo, aunque siempre obtienes, por ejemplo, 13 cartas.
2. A diferencia de una matriz que es una estructura efectiva en cuanto a la memoria, ya que se crea en la parte cohesiva de la memoria, cuando crea una lista, debe permitir agregar nuevos elementos al medio, etc., por lo que solo necesita asignar nueva memoria para cada celda , lo que la convierte en una estructura muy ineficiente, pero también está sujeta a factores aleatorios como dónde se asignó exactamente la celda. Una de sus listas podría ser más afortunada con respecto al caché (depende también de cómo los creó, si acaba de crear el primer elemento, luego el segundo y el tercero, de lo que posiblemente no haya tanta diferencia en comparación con si los creó al azar al agregar y eliminar elementos).