动态数组推送VS分配给静态大小数组:JavaScript中的时间复杂度

laawzig2  于 2023-03-11  发布在  Java
关注(0)|答案(2)|浏览(88)

我有一个动态数组,如下所示:

const array1 = [];

    for(let i = 0; i < 5; i++)
    array1.push(i+1);

和另一个阵列:

let Array2 = Array(6); //Note here the size is 6 as compared to the array1 which has initial size as 5.

for(let i = 0; i < 5; i++)
        Array2[i] = i+1;

现在我想在数组的最后添加一个元素,如下所示:
array1.push(6);
上面的操作将是O(n),因为这个过程将导致array1被移动到一个新的数组,然后在末尾附加6,还是仅仅是O(1)。
另外,哪种声明更好?const array1 = [],然后向其中添加元素,或者初始化一个空数组(大小已知),然后逐个替换元素。
下面是同样的例子:
已知前五个元素来自for循环(其调用另一函数),并且最后一个元素来自函数getElement,如下所示:
Method 1:

const Array1 = [];

for(let i = 0; i < 5; i++)
Array1.push(getFirstFiveElements(i));
//Where getFirstFiveElements is another function


Array1.push(gettheSixthElement());

Method 2

const Array2 = Array(6);
for(let i = 0; i < 5; i++)
Array2[i] = getFirstFiveElements(i);


Array2[Array2.length - 1] = gettheSixthElement();
oxosxuxt

oxosxuxt1#

初始化一个已知大小的数组总是比较好的,因为当你把元素推到一个缺少所需空槽数的数组上时,JavaScript必须在后台将现有的底层数组复制到一个新数组中,新数组的大小是旧数组的两倍。因此,向数组中添加值不是O因为有时候它会导致整个数组被复制。然而如果你用一个已知的大小初始化数组,那么所有的加法运算都是O(1)。

bxjv4tth

bxjv4tth2#

为什么我们需要初始化长度?理论上没有这个必要。它甚至会导致混乱的行为,因为所有使用长度来查找数组是否为空的测试都会报告数组不为空。一些测试表明,如果数组在以后填充,则设置大型数组的初始长度会更有效。但是性能增益(如果有的话)似乎因浏览器而异。

相关问题