Space 函数的复杂度

Question

我刚开始计算 space 复杂性，并且无法计算以下函数

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。

提前感谢您的帮助

Answer 1

是的，它是恒定的，因为无论您的输入有多大，集合都可能有一个最大大小。

事实上，如果 string.length <= 128 限制不存在，它甚至仍然是常量，只要函数需要 string 而不是数组任意项目，因为字符串的特点是由 UTF-16 字符组成，其中只有有限的数量 - 无论输入多长，该集合永远不会超过字母表的大小。

Space 函数的复杂度

Space complexity of function

javascript

big-o

complexity-theory

space