python - python中生成器表达式的时间复杂度

Question

我正在解决给定两个字符串的问题s和t，目的是找出是否s是 的子序列t。我遇到了一个解决方案：

def isSubsequence(s, t):
   t = iter(t)
   return all(c in t for c in s)

我想知道这个解决方案的时间复杂度是多少。这是我发现的：

首先，我们变成t了一个迭代器，它的作用是c in t遍历迭代器，直到它找到匹配的第一个位置。其次，c in t for c in s是一个生成器：它返回一个迭代器。第三，all()将迭代器作为参数并循环查找第一个False. 如果找不到，则返回True。

迭代的 for 循环s具有 O(s) 复杂度，假设是O(t) 复杂度c中的最后一个字母。t此外，由于这与嵌套的 for 循环不同，因此复杂度不会是 O(s * t)。你能在这种情况下帮助我吗？

标签： pythontime-complexity

Answer 1

一个迭代器只能被遍历一次。例如，

>>> t = iter([1,2,3])
>>> list(t)
[1, 2, 3]
>>> list(t)
[]
>>> list(t)
[]

该函数利用了这样一个事实，即c in t只消耗必要的迭代器来确定c是否找到。找到时c，迭代会停止，直到您下一次评估c in t，此时您从中断处继续t。一旦到达末尾t，所有进一步的调用c in t都会立即返回，因为迭代器不会自行重置。因此，all(c in t for c in s)将len(s)调用c in t，但在这些调用过程中累积len(t)的比较次数为; 您t最多只能查看原始参数的每个元素。