Python 中的“for ... in”循环会增加空间复杂度吗？

Question

假设我有以下功能：

def findNumVowels(s):

    vowels = ['a', 'e', 'i', 'o', 'u']

    numVowels = 0

    for char in s:

        if char in vowels:

            numVowels += 1

    return numVowels

print(findNumVowels("hello world")) # 3

for ... in循环是否会通过为每个charin创建一个新字符串来增加此函数的空间复杂度s，还是这种语法糖抽象了我们正在访问字符串的特定索引这一事实？

Answer 1

不，循环本身没有。考虑：for char in some_string:     print(char)它只需要一个固定大小的额外对象。这相对于字符串的大小是恒定的。所以，不管我的字符串是 10 还是 1000 个字符长都没有关系，它总是需要一个额外的str来循环它。因此，它需要恒定的空间。

Answer 2

首先，您关心的答案是 for 循环实际上不会增加空间复杂度。但是，如果您使用大型数组，则 for 循环的时间复杂度非常低。建议使用矢量化操作而不是 multi for 循环。例如，numpy.dot()这在机器学习或深度学习中很常见。

Answer 3

这是一个带有列表理解的版本：def findNumVowels(s):    vowels = ['a', 'e', 'i', 'o', 'u']    return len([char_literal for char_literal in s if char_literal in vowels])findNumVowels("Kunal")如您所见，Python 字符串是不可变的，这意味着它们在创建后无法更改。所以我们只是用 for..in 构造索引字符串，这不会占用任何额外的空间复杂度。