我正在寻找这个问题的答案，但找不到任何答案。

new Array(n).fill('apple') 的时间复杂度是多少？

对于 n=5，这将创建一个包含 5 个“apple”字符串的数组:['apple', 'apple', 'apple', 'apple', 'apple' ]

我的假设是 new Array(5) 将首先创建一个包含 5 个空槽的数组，然后遍历它以将“apple”放入每个槽中。 这样的话，时间复杂度是O(N)，N是数组的长度？

但是，我也听说有人说因为它是一个内置方法，所以只需要 O(1)。

最佳答案

时间复杂度应为 O(N)，因为它应与数组的长度成线性比例。

为了验证该理论，我运行了一些基准测试以查看它是否实际上是 O(n)。

对于较大的数组，nodejs 在测量时显示大约 O(n)(请参见下面的代码和结果)。

我用 5 种尺寸的阵列运行这个测试应用。

const sizes = [1000, 10000, 100000, 1000000, 1000000];

然后，计算 process.hrtime.bigint() 需要多长时间。然后我输出每个大小数组的总时间(以纳秒为单位)和每个元素的时间。

这是我得到的输出:

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 ]

您可以看到最后三个大小非常接近于 O(n)，每个元素的固定时间有大约 5% 的变化(正好是 O(n) )。第一个距离很远，第二个在每个元素上比其他的稍微快一些，尽管与最后三个在同一个大球场上。

第一遍必须有某种解释器开销(可能优化代码路径)，或者操作的总开销可能比实际填充数组要多得多，以至于扭曲了我们试图测量的内容。

代码如下:

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);

关于javascript - new Array(n).fill ('apple' ) 在 JavaScript 中的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69336023/