Estuve buscando la respuesta a esta pregunta pero no pude encontrar ninguna.
¿Cuál es la complejidad temporal de new Array(n).fill('apple') ?
Para n=5 , esto creará una matriz con 5 cadenas de 'manzana': ['apple', 'apple', 'apple', 'apple', 'apple']
Mi suposición es que new Array (5) primero creará una matriz con 5 ranuras vacías y luego iterará a través de ella para poner 'apple' en cada ranura. En este caso, la complejidad del tiempo es O(N), ¿N es la longitud de la matriz?
Sin embargo, también escuché que algunos dicen que, dado que es un método integrado, solo tomará O (1).
Debe ignorar la complejidad del algoritmo cuando trabaja con una matriz de cadenas con una longitud de 5 elementos. Pero en este caso, llena la matriz con los mismos valores. En este caso:
Array(5).fill('apple')es una solución más elegante por razones de estilo de código
PS O(1) + O(n) => O(n)
La complejidad del tiempo debe ser O(N) , ya que debe escalar linealmente con la longitud de la matriz.
Para probar esa teoría, realicé algunos puntos de referencia solo para ver si realmente parece ser O(n) .
Para arreglos más grandes, nodejs muestra aproximadamente O(n) cuando lo mide (consulte el código y los resultados a continuación).
Ejecuto esta aplicación de prueba con 5 tamaños para la matriz.
const sizes = [1000, 10000, 100000, 1000000, 1000000]; Y mida cuánto tiempo lleva con process.hrtime.bigint() . Luego presento el tiempo total para cada matriz de tamaño en nanosegundos y el tiempo por elemento.
Esta es la salida que obtengo:
Array sizes: [ 1000, 10000, 100000, 1000000, 1000000 ] Ns per pass: [ 36700n, 48600n, 553000n, 5432700n, 5268600n ] Ns per element: [ 36.7, 4.86, 5.53, 5.4327, 5.2686 ] Puede ver que los últimos tres tamaños están muy cerca de O(n) con alrededor de un 5% de variación de un tiempo fijo por elemento (que sería exactamente O(n) ). El primero está muy lejos y el segundo es un poco más rápido por elemento que los demás, aunque en el mismo estadio general que los tres últimos.
El primer paso debe tener algún tipo de sobrecarga del intérprete (quizás optimizando la ruta del código) o tal vez solo la sobrecarga general de la operación es mucho más que llenar la matriz que distorsiona lo que estamos tratando de medir.
Aquí está el código:
class Measure { start() { this.startTime = process.hrtime.bigint(); } end() { this.endTime = process.hrtime.bigint(); } deltaNs() { return this.endTime - this.startTime; } deltaNumber() { return Number(this.deltaNs()); } } const sizes = [1000, 10000, 100000, 1000000, 1000000]; const benchmark = new Measure(); const times = sizes.map(size => { benchmark.start(); new Array(size).fill('apple'); benchmark.end(); return benchmark.deltaNs(); }); console.log('Array sizes:\n', sizes); console.log('Ns per pass:\n', times); let factors = times.map((t, index) => { return Number(t) / sizes[index]; }); console.log('Ns per element:\n', factors);