python - 是 python 设置 s.difference_update(t) O(m X n)

Question

问题陈述:

我正在处理一个问题，我有一个数据库，其中包含来自文件系统的大量文件。如果从系统中删除了一堆文件，则应在数据库中更新相同的文件。

方法:

查询数据库中的文件列表和文件系统中的文件列表。然后比较来自 db 的每个文件是否在另一个列表中。找不到就删除为了避免重复从列表中查找每个文件，我打算在 python 中使用集合和 difference_update() 方法

问题:

在内部，这是否会再次具有 O(m X n) 的复杂性，就像重复搜索的其他方法一样，还是经过优化以降低复杂性？

Answer 1

如评论中所述，它将是 O(len(t))，因为设置了常量查找时间。
也在http://python-reference.readthedocs.org/en/latest/docs/sets/difference_update.html中确认