¿Usar un tipo de inserción de 50 elementos tendrá el mismo tiempo de ejecución que usar un tipo de inserción de 10 elementos 5 veces?

¿No tendría sentido ejecutar esto y averiguarlo?

Mientras configura su experimento, tenga en cuenta lo siguiente:

1. ¿Cuánta variación de carrera a carrera ves ejecutando el mismo experimento varias veces? Para creer sus resultados, ¿cuántas ejecuciones necesita hacer antes de que sus resultados sean estadísticamente significativos?
2. ¿Cómo afectaría el tamaño del elemento a insertar a sus resultados? En particular, ¿cuál esperaría que fuera la diferencia entre insertar un objeto del tamaño de caché versus un puntero a un objeto del tamaño de caché?
3. ¿Cómo afectaría el tamaño de la lista a sus resultados? ¿Qué sucede si su lista no cabe dentro del caché? ¿Qué sucede cuando llena la mayor parte de la memoria? ¿O cuándo es demasiado grande para la memoria y reside principalmente en el disco?
4. ¿Cómo cambian sus resultados cuando las ubicaciones de inserción están juntas? ¿Ampliamente espaciado? ¿Aleatorio?
5. Bonificación: ¿cómo cambiaría la inserción paralela sus resultados?

Deje elegir el conjunto de elementos de orden inverso. Asumiremos una lista vinculada para que las inserciones sean baratas.

Con tal conjunto, el número de comparación viene dado por:

[matemáticas] \ frac {n ^ 2 + n} {2} [/ matemáticas]

Entonces, para 50 elementos, tenemos 1275 comparaciones:

[matemáticas] \ frac {51 \ veces 50} {2} [/ matemáticas]

Ahora, veamos 10 elementos 5 veces:

[matemáticas] 5 \ veces \ frac {11 \ veces 10} {2} [/ matemáticas]

Solo baraja un poco las cosas:

[matemáticas] \ frac {10 \ veces11 \ veces 10} {2} [/ matemáticas]

Ahora podemos simplificar estas dos expresiones:

[matemáticas] \ frac {51 \ veces 50} {2} [/ matemáticas]

[matemáticas] \ frac {10 \ veces11 \ veces 10} {2} [/ matemáticas]

Se convierte en:

[matemáticas] 51 [/ matemáticas]

[matemáticas] 22 [/ matemáticas]

Entonces, en ese caso, el segundo es más rápido.

Si tenemos el conjunto totalmente ordenado, insertaremos elementos en la parte delantera en cada caso. Tendremos la misma cantidad de comparación para cada artículo (uno).

El orden de inserción es O (n²). Estos algoritmos están bien para valores pequeños de n y rápidamente se vuelven inútiles. Otros algiloritmos son O (log (n)) y son más adecuados para grandes n debido a su costo inicial. (Debe tener alguna estructura en su lugar o preparar sus datos)

Además, utilizamos una lista vinculada para tener inserciones baratas. Algunos algoritmos requieren estructuras dedicadas.

Lo que inserte puede ser lento para comparar, rápido para insertar. Por lo tanto, es posible que desee minimizar las comparaciones. Puede ser al revés, los datos son fáciles de comparar, pero lentos para insertar.

O peor aún: está leyendo desde una cinta magnética y tendrá la oportunidad de leer el elemento solo una vez. Para empeorar las cosas, es posible que pueda manejar solo unos pocos elementos en la memoria. Por lo tanto, querrá minimizar el número de lecturas de cinta.

Un tipo interesante es el tipo de sueño.

para (i = 0; i asíncrono {
dormir (i);
imprimir (i);
}
}

Versión Js:

var a = [1,3,2,9,6,8,7];
para (i = 0; i <7; i ++) {
setTimeout (function () {var j = i; console.log (j);}, i * 100);
}