代码之家 › 专栏 › 技术社区 › ababuji

空间复杂度:用键初始化哈希图并单独更新其值。

space-complexity time-complexity hashmap python-3.x python

1

ababuji · 技术社区 · 6 年前

假设我有一个简单的问题,涉及返回字符串中所有字符的出现索引。我知道你可以直接运行一个for循环并打印出来,但是假设我必须以某种数据结构返回它!

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

我可以做两件事之一。

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

遍历dictionary元素,并删除那些键、值值为的对 无 .

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)

初始化没有键或值的空哈希映射。

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

ascii_occurrence = {}

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

print(ascii_occurrence)

我确信这两种情况下的时间复杂度都是O(n),但我不确定这两种方法的空间复杂度。

关于空间复杂性的争论:

方法1,我的空间不依赖于输入的大小。您可以假设当您购买计算机以运行此特定用途的代码时,已经存在128个键的哈希图。我只更新值,不创建新的键,也不根据输入扩展hashmap。在这种情况下是O(1)。

方法2,hashmap最初是空的,没有任何内容,您必须通过遍历字符串来用键、值对填充它。真的。。词典的填充量取决于输入的大小。在这种情况下是O(N)。

我的论点正确吗?

1 回复 | 直到 6 年前

1

2

Mazdak 6 年前

这两种方法的复杂性是O(n ^ 2),这是因为在每次迭代中都有索引。 string[charIndex] ). 不过,在这种情况下,第二种方法通常是更好的方法。但是,您也可以使用字典理解以更优化的方式(就运行时而言)执行此操作,如下所示:

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

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

这个片段在运行时间和内存方面的复杂性当然是O(n)。

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

ascii_occurrence = dict(enumerate(string))