Пространственная сложность функции - PullRequest
Новая
       62

Пространственная сложность функции

1 голос
/ 12 апреля 2020

Я новичок в разработке сложности пространства и застрял, выполняя следующую функцию 

const isUnique = string => {
  if (string.length > 128) {
    return false
  }

  let seen = new Set()

  for (let i = 0; i < string.length; i++) {
    if (seen.has(string[i])) {
      return false
    }
    seen.add(string[i])
  }

  return true
}

Будет ли O (n), поскольку набор будет расти пропорционально размеру строки? Или O (1), поскольку он является единичным множеством, независимо от его размера и никогда не превысит 128.

Заранее благодарен за любую помощь

1 Ответ

4 голосов
/ 12 апреля 2020

Да, это константа, потому что есть максимальный размер, который может иметь набор, независимо от того, насколько велик ваш ввод.

Фактически, он даже будет постоянным, если бы не было ограничения string.length <= 128 до тех пор, пока функция ожидает строку , а не массив произвольных элементов, поскольку строка характеризуется тем, что состоит из символов UTF-16, число которых ограничено - набор никогда не будет расти за пределами размера алфавита, независимо от длины ввода.

...