在for循环中使用reduce使代码的复杂度为O(n)或更高，如O(n^2)或其他类型

Question

面试时，他们让我做一些练习，第三个练习如下：

在具有随机整数的向量/数组v1中，我们有未知数量的元素。

• 制作了一个长度与v1相同的v2向量/数组，因为v2[k]是v1中除v1[k]之外的所有元素的乘积
• 尝试在没有除法运算符并且具有复杂性O(n(的情况下进行

我执行以下代码：

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7]; //it's just an example array
const l = v1.length;
let v2 = [];
for (let i = 0; i < l; i++) {
let segment = v1.splice(0, 1); // save the number of the position in array that it'll exclude de product
let product = v1.reduce((total, number) => { return total * number; }, 1);
v2.push(product); // add the result to the v2 array at the position of the number of v1 array
v1.push(segment); // is necesary to add again the segment of the v1 array to keep the original length
}
console.log('v2', v2);
/* Results Reference
product of all array    42674688    
product - position 00   10668672    
product - position 01   21337344    
product - position 02   6096384 
product - position 03   5334336 
product - position 04   7112448 
product - position 05   6096384 
product - position 06   4741632 
product - position 07   14224896    
product - position 08   21337344    
product - position 09   7112448 
product - position 10   6096384  
*/

我的问题是：

• 我的代码是O(n(复杂度吗？还是O(n^2(？还是另一种复杂性

感谢

Answer 1

您的代码不是O(n(，因为对于数组v1的每个元素，您都运行贯穿整个数组的.reduce()函数，所以它是O(n^2(。

您可以通过计算总乘积，然后通过v1数组迭代一次，并将total / current推送到v2数组来实现。这样，您将获得具有O(n(复杂性的所需结果。

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7];
const v2 = [];
const productTotal = v1.reduce((res, curr) => res * curr);
v1.forEach((el) => v2.push(productTotal/el));
console.log(v2);

所以总的来说，你在v1数组中迭代两次——一次计算productTotal，一次计算v2，所以事实上，这是一个O(2n(的复杂度，但我们可以忽略2，因为它仍然是O(n(。

要在不除法的情况下实现它，你可以使用一个技巧，而不是直接使用除法，你可以用乘法和-1的幂(不知道这是否算数(：

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7];
const v2 = [];
const productTotal = v1.reduce((res, curr) => res * curr);
v1.forEach((el) => v2.push(productTotal*Math.pow(el, -1)));
console.log(v2);

Answer 2

正如@Sebastian Kaczmarek已经回答的那样，由于.reduce的时间复杂度是O(n(，并且.reduce在贯穿整个数组的for循环中，因此代码的时间复杂程度是O(n^2(。

时间复杂度为O(n(且不使用除法运算符的一种可能的解决方案如下：

const v1 = [4, 2, 7, 8, 6, 7, 9, 3, 2, 6, 7];
const length = v1.length;
const v2 = new Array(length);
const listOfAccFromStart = new Array(length);
const listOfAccFromEnd = new Array(length);
let accFromStart = 1;
for (let i = 0; i < length; i++) {
accFromStart *= v1[i];
listOfAccFromStart[i] = accFromStart;
}
let accFromEnd = 1;
for (let i = length - 1; i >= 0; i--) {
accFromEnd *= v1[i];
listOfAccFromEnd[i] = accFromEnd;
}
v2[0] = listOfAccFromEnd[1];
v2[length - 1] = listOfAccFromStart[length - 2];
for (let i = 1; i < length - 1; i++) {
v2[i] = listOfAccFromStart[i - 1] * listOfAccFromEnd[i + 1];
}
console.log('v2', v2);

它保存从开始到listOfAccFromStart的累积乘积值和从结束到listOfAccFromEnd的累积乘积。并使用保存的值设置v2。其时间复杂度为O(n(，空间复杂度为0(n(。