当我们遍历字符串时用输入字符串的索引更新字典 - O(n) 或 O(1) space 复杂度？

Question

我的问题是关于 Space 使用 input string 更新 dictionary 的复杂性。

例如string = "thisisarandomstring"、my_dict = dict()

假设我们遍历输入字符串，对于每个字符，我们存储和更新最新字符的索引。

即

for i in range(len(string)): 
    my_dict[string[i]] = i

上面的 space complexity 会是 O(n)? Or O(1) 吗？

我正在解的题中解说是O(n)，但是按照我的理解，我们最多只能在字典中存储26个字符，所以不应该是O(1)吗？我可以看到更新的次数取决于输入字符串的长度，但这会影响 space 吗？由于对于每次更新，我们都会替换之前看到的元素的先前索引。

Answer 1

你是对的，最终我们可以在dictionary中存储26个不同的键，因此dictionary消耗的space将是常量，即O(1)。但是，您正在创建一个包含 n 个字符的 string 变量。存储长度为 n 的新字符串的 space 复杂度为 Θ(n)，因为每个单独的字符都必须存储在某处。因此，这可能是它被表示为 O(n).

的原因

顺便说一句，如果我们将 space 复杂度（消耗的 space 量）表示为 f(n)。那么f(n)∈O(1)表示f(n)∈O(n)。因此 f(n) ∈ O(n) 不是一个错误的陈述。好吧，从技术上讲。

当我们遍历字符串时用输入字符串的索引更新字典 - O(n) 或 O(1) space 复杂度？

Updating a dictionary with index of an input string as we iterate over the string- O(n) or O(1) space complexity?

python

space-complexity