Какова продолжительность выполнения вложенного l oop? - PullRequest
Новая
       37

Какова продолжительность выполнения вложенного l oop?

0 голосов
/ 05 мая 2020

Я пытаюсь стать лучше в кодировании, поэтому после каждого испытания хакерского ранга я проверяю, что сделали другие люди, чтобы я мог сравнить свой код с их кодом. Одно из интересных решений, которое, по-видимому, работает, это: 

function getMoneySpent (keyboards, drives, b) {
  return keyboards.reduce (
    (acc, curr) =>
      Math.max (acc, ...drives.map (usb => usb + curr).filter (ku => b >= ku)),
    -1
  );
}

console.log (getMoneySpent ([1, 20, 40], [5, 60, 7], 50));

Он в основном находит максимальную сумму двух чисел (по одному из каждого массива), которые являются <= числом (в данном случае 50). Однако, когда я проанализировал код, мне показалось, что есть два цикла: <code>.reduce и .map с .filter. Делает ли это код O (n) ^ 2? Я почти уверен, что в противном случае он не прошел бы тесты, поскольку массивы могут быть длиной 1000, а число (50) может быть 10 ^ 6. Вот ссылка на проблему, если интересно.

В конце концов, мой вопрос - это код O (n) ^ 2?

1 Ответ

0 голосов
/ 05 мая 2020

Насколько я понимаю, это на самом деле 3•O(n)^2

Рассуждения см. Ниже: 

function getMoneySpent (keyboards, drives, b) {
                // O(n)
  return keyboards.reduce ( 
    (acc, curr) =>
        // O(n) +              O(n) +                  O(n)
      Math.max (acc, ...drives.map (usb => usb + curr).filter (ku => b >= ku)),
    -1
  );
}

O(n) * (O(n) + O(n) + O(n))
O(n) * 3•O(n)
3•O(n)^2

Исходный код Math.max

...