python - 找到回文python空间复杂度？

Question

给定以下 python 代码，它检查 n 大小的字符串是否为回文:

def is_palindromic(s):
    return all(s[i] == s[~i] for i in range(len(s) // 2))

这段代码的空间复杂度是多少？是 O(1) 还是 O(n)？

all 函数 gets一个可迭代的参数；

这是否意味着 s[i] == s[~i] for i in range(len(s)//2) 表达式是一个可迭代(容器)，它存储 n 内存中的值？

或者它可能表现得像一个迭代器，在没有任何额外空间的情况下一个一个地计算并返回值？

Answer 1

您正在使用 generator expression, which only needs enough memory to store one item at a time .

其他部分，len、range 和 all 函数本身也是 O(1)，所以你的建议是“它表现得像一个迭代器，在没有任何额外空间的情况下一个一个地计算和返回值”是正确的。

如果你改用列表表达式

all([s[i] == s[~i] for i in range(len(s) // 2)])

它将短暂地使用 O(n) 内存来构建列表，该列表将作为参数传递给 all。