Space 复杂性：使用键初始化哈希映射并单独更新其值与在循环内动态填充键、值对

Question

假设我有一个简单的问题，涉及 return 字符串中所有字符的出现索引。我知道您可以直接运行一个 for 循环并将其打印出来，但假设我必须 return 它在某些数据结构中！

其他假设：我们知道这是一个 ASCII 字符串。字符串中不存在重复字符。

我可以做两件事之一。

预先用所有可能的 128 个键初始化 hashmap 和 None 作为值。
遍历字符串并简单地更新 dictionary/hashmap
以索引作为键的值。

遍历字典元素，并删除那些键，值值为 None.

的对

ascii_occurrence = {'a': None, 'b': None, 'c': None ... char#128: None} #Initialize a hashmap with each of the 128 characters as key, and set None to its value.

for charIndex in string:
    ascii_occurrence[string[charIndex]] = charIndex

indexMap = {k: v for k, v in ascii_occurrence.items() if v is not None}

print(indexMap)

初始化一个没有键或值的 EMPTY hashmap。

遍历字符串并创建键值对。

ascii_occurrence = {}

for charIndex in string:
    ascii_occurrence[string[charIndex]] = charIndex

print(ascii_occurrence)

我确定这两种情况下的时间复杂度都是 O(N)，但我不确定这两种方法的 space 复杂度。

关于 space 复杂性的争论：

方法 1，我的 space 没有 "DEPEND" 输入的大小。您可以假设当您购买计算机时已经存在具有 128 个键的散列图运行用于此特定目的的代码。我只是更新值而不是创建新键并根据我的输入扩展散列图.在这种情况下是 O(1).

方法 2，hashmap 最初是空的，里面什么也没有，您必须通过遍历字符串来用键值对填充它。所以真的.. 你填充字典的数量取决于输入的大小。在这种情况下是 O(N)。

我的说法正确吗？

Answer 1

这两种方法的复杂度都是 O(N^2)，这是因为您在每次迭代时都有一个索引 (string[charIndex])。但是，在这种情况下，您的第二种方法通常是更好的方法。但是您也可以使用字典理解以更优化的方式（根据运行时间）进行操作，如下所示：

ascii_occurrence = {charIndex: ind for ind, charIndex in enumerate(string)}

在这种情况下，除了不获取带有索引的字符外，您不需要将项目分配给先前创建的字典。相反，Python 将根据需要为您创建字典，这将节省您在每次迭代时调用 __setitem__ 函数的时间，它本身是暂停和恢复函数框架的组合。

这段代码的复杂度在运行时间和内存方面当然是 O(N)。

现在，如果您正在寻找一种更优化的方法，这很容易实现，但您必须牺牲一些其他的东西。这就是说，如果你想要更少的运行时间，你应该放弃一些内存，反之亦然。但是如果你不想这样做，你可能想考虑在你到达这一点之前创建你的字典。您可以在创建主字符串时创建字典。您还可以在此处执行其他棘手的方法，例如通过将枚举对象直接传递给 dict 对象来直接从枚举对象创建 dict。但在这种情况下，索引将是键，字符将成为值。

ascii_occurrence = dict(enumerate(string))

Space 复杂性：使用键初始化哈希映射并单独更新其值与在循环内动态填充键、值对

Space complexity: initializing a hashmap with keys and updating its values alone vs. dynamically populating key, value pairs inside a loop

python

hashmap

time-complexity

space-complexity

python-3.x