Space 在字符串中查找非重复字符的复杂性

Question

这是一个简单的算法练习。问题是 return 第一个非重复字符。例如，我有这个字符串：'abbbcdd'，答案是 'a'，因为 'a' 出现在 'c' 之前。如果它没有找到任何重复的字符，它将 return '_'.

我的解决方案工作正常，但我的问题是关于性能。问题陈述说："Write a solution that only iterates over the string once and uses O(1) additional memory."

这是我的代码：

console.log(solution('abbbcdd'))

function solution(str) {
  let chars = buildCharMap(str)
  for (let i in chars) {
    if (chars[i] === 1) {
      return i
    }
  }
  return '_'
}

function buildCharMap(str) {
  const charMap = {}
  for (let i = 0; i < str.length; i++) {
    !charMap[str[i]] ? charMap[str[i]] = 1 : charMap[str[i]]++
  }
  return charMap
}

我的回答是否满足 space 复杂性的要求？

Answer 1

时间复杂度很简单：你有一个循环遍历一个长度为 n 的字符串，另一个循环遍历一个严格最多为 n[= 的对象44=] 键。循环内的操作需要 O(1) 时间，并且循环是连续的（没有嵌套），所以运行时间是 O(n).

space 的复杂性稍微微妙一些。例如，如果输入是数字列表而不是字符串，那么我们可以直接说 charMap 在最坏情况下需要 O(n) space case，因为列表中的所有数字可能都不同。但是，对于字符串问题，我们必须意识到可以构成这些字符串的字符的字母表是有限的。如果该字母表的大小为 a，那么您的 charMap 对象最多可以有 a 个键，因此 space 复杂度是 O(min(a, n)).

该字母表在问题中通常是明确的 - 例如，如果输入保证仅包含小写字母，或仅包含字母和数字。否则，它可能隐含在字符串由 Unicode 字符（或旧语言中的 ASCII 字符）构成的事实中。在前一种情况下，a = 26 或 62。在后一种情况下，a = 65,536 或 1,112,064 取决于我们是否在计算 代码单元或代码点，因为Javascript字符串被编码为UTF-16。无论哪种方式，如果 a 是常数，则 O(a) space 是 O(1) space -尽管它可能是一个相当大的常数。

这意味着在实践中，您的算法确实使用 O(1) space。理论上，如果问题陈述指定一个固定的字母表，它使用 O(1) space，并且 O(min(a, n)) space 否则;不是 O(n) space。假设是前者，那么您的解决方案确实满足问题的 space-复杂性要求。

这提出了一个问题，为什么在分析数字列表的算法时，我们不会同样说 Javascript 数字具有由 IEEE 754 specification 定义的有限 "alphabet"浮点数字。答案有点哲理；我们使用抽象计算模型分析运行时间和辅助 space，这些模型通常假设数字、列表和其他数据结构对其大小没有固定限制。但即使在那些模型中，我们假设字符串是由一些字母表组成的，如果字母表在问题中没有固定，那么我们让字母表大小成为一个变量 a 我们假设是独立于 n。这是分析字符串算法的明智方法，因为字母大小和字符串长度在我们通常感兴趣的问题中是独立的。

Space 在字符串中查找非重复字符的复杂性

Space complexity of finding non-repeating character in string

javascript

performance

big-o

space-complexity