Пространственно-временная сложность двух разных подходов - PullRequest
Новая
       5

Пространственно-временная сложность двух разных подходов

0 голосов
/ 27 октября 2019

Я пытаюсь научиться оценивать временную и пространственную сложность различных итераций и мне нужна помощь с моим вторым подходом. В чем разница с точки зрения сложности пространства и времени для этих двух функций ниже?

Это должно быть O(n) время и O(n) пространство. 

function twoNumberSum(array, targetSum) {
  let nums = {};

  for (const num of array) {
    const potentialMatch = targetSum - num;

    if (potentialMatch in nums) {
      return [potentialMatch, num].sort((a, b) => a - b)
    } else {
      nums[num] = true
    }
  }

  return []
}

console.log(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10))

Однако этот подход? 

function twoNumberSum(array, targetSum) {
  const map = new Map(array.map(item => [item, item]));

  for (let [key, value] of map) {
    const missingInc = targetSum - value;
    if (missingInc !== value && map.has(missingInc)) {
      return [value, map.get(missingInc)].sort((a, b) => a - b)
    }
  }

  return [];
}

console.log(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10))

Кроме того, последний вопрос ... когда я сортирую инструкцию возврата с .sort((a, b) => a - b), следует ли это определить как O(log(n))?

1 Ответ

2 голосов
/ 27 октября 2019

Я бы предложил сначала провести их рефакторинг, чтобы использовать ту же структуру данных, чтобы различия стали более заметными: 

function twoNumberSum(array, targetSum) {
  let nums = new Set();
  for (const num of array) {
    const potentialMatch = targetSum - num;
    if (nums.has(potentialMatch) {
      return [potentialMatch, num].sort((a, b) => a - b)
    } else {
      nums.add(num)
    }
  }
  return []
}


function twoNumberSum(array, targetSum) {
  const nums = new Set();
  for (const num of array)
    nums.add(num);
  // alternatively, use const nums = new Set(array), but the loop is clearer
  for (let num of array) {
    const missingInc = targetSum - num;
    if (missingInc !== value && nums.has(missingInc)) {
      return [value, missingInc].sort((a, b) => a - b)
    }
  }
  return [];
}

Прежде чем рассматривать производительность, нам нужно оценитьправильность / эквивалентность: обратите внимание, что вторая функция не работает, когда входное значение содержит дубликаты. Но давайте предположим, что это задано как предварительное условие (никогда не может произойти), и в этом случае результаты всегда одинаковы.

Разница в том, что один подход всегда строит всю карту поиска перед тестированием значений, в то время какдругие строят это на ходу. Хотя оба варианта имеют O(n) сложность наихудшего случая, для первого подхода сложность наилучшего случая равна O(1), а для второго - O(n). Какова средняя сложность зависит от того, как распределены ваши входные данные.

Когда я сортирую инструкцию возврата с .sort((a, b) => a - b), следует ли это определить как O(log(n))?

Нет. Сложность сортировки обычно O(n log n), но где n относится к длине массива, который будет отсортирован. В вашем случае вы всегда сортируете массив из двух элементов, который имеет постоянную сложность. Он не зависит от размера ввода n (предполагается, что array.length, хотя в некоторых числовых задачах вам также необходимо учитывать размер чисел).

...