используя сокращение внутри a для l oop, сделайте код сложности O (n) или выше, например O (n ^ 2) или другого вида?

Question

Для собеседования они просят меня сделать несколько упражнений, и третье из них было следующим:

У нас есть неизвестное количество элементов в векторе / массиве v1 со случайными целыми числами.

• Создал вектор / массив v2 с той же длиной v1, в которой 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

Поскольку уже ответил от @ Sebastian Kaczmarek , временная сложность вашего кода составляет O (n ^ 2), поскольку временная сложность .reduce равна O ( n) и .reduce находятся в for l oop, который проходит через весь массив.

Одно возможное решение, временная сложность которого составляет 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), а его пространственная сложность - O (n).

Answer 2

Ваш код не 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);