设置函数转换列表的时间复杂度，反之亦然

Question

我正在将列表转换为集合并返回列表。我知道 set(list) 需要 O(n) 时间，但我正在将它转换回同一行 list(set(list)) 中的列表。由于这两个操作都需要 O(n) 时间，所以时间复杂度现在是 O(n^2) 吗？

逻辑 1：

final = list(set(list1)-set(list2))

逻辑 2：

s = set(list1)-set(list2)
final = list(s)

这两种实现是否具有不同的时间复杂度，如果有，哪一种更有效？

Answer 1

不需要进行一次集合转换，因为 set.difference 可以按应有的方式处理任何可迭代对象：

final = list(set(list1).difference(list2))

但是整个事情的渐近时间和space复杂度仍然是O(m+n)（两个列表的大小）。

Answer 2

在这两个版本中你正在做的：

将列表转换为集合
将另一个列表转换为集合
减去两组
将结果集转换为列表

其中每一个都是 O(n)，其中 n 是两个起始列表大小的界限。

那是四次 O(n)，所以总的来说是 O(n)。

你的两个版本本质上是一样的。

Answer 3

您的两个版本相同，从 dis:

>>> dis.dis("list(set(list1) - set(list2))")
  1           0 LOAD_NAME                0 (list)
              2 LOAD_NAME                1 (set)
              4 LOAD_NAME                2 (list1)
              6 CALL_FUNCTION            1
              8 LOAD_NAME                1 (set)
             10 LOAD_NAME                3 (list2)
             12 CALL_FUNCTION            1
             14 BINARY_SUBTRACT
             16 CALL_FUNCTION            1
             18 RETURN_VALUE
>>> dis.dis("s = set(list1) - set(list2);list(s)")
  1           0 LOAD_NAME                0 (set)
              2 LOAD_NAME                1 (list1)
              4 CALL_FUNCTION            1
              6 LOAD_NAME                0 (set)
              8 LOAD_NAME                2 (list2)
             10 CALL_FUNCTION            1
             12 BINARY_SUBTRACT
             14 STORE_NAME               3 (s)
             16 LOAD_NAME                4 (list)
             18 LOAD_NAME                3 (s)
             20 CALL_FUNCTION            1
             22 POP_TOP
             24 LOAD_CONST               0 (None)
             26 RETURN_VALUE
>>>

这两者之间的唯一区别是第二个将它存储到一个变量s，所以它必须LOAD_NAME 名称s。在第一个代码中，list 首先被调用，但在第二个代码中，get 稍后被调用。

但是在@user2390182 的回答中，它加载的不是第二次加载 set LOAD_NAME，而是加载函数名称 difference，IMO 在这里是最有效的：

>>> dis.dis("list(set(list1).difference(list2))")
  1           0 LOAD_NAME                0 (list)
              2 LOAD_NAME                1 (set)
              4 LOAD_NAME                2 (list1)
              6 CALL_FUNCTION            1
              8 LOAD_METHOD              3 (difference)
             10 LOAD_NAME                4 (list2)
             12 CALL_METHOD              1
             14 CALL_FUNCTION            1
             16 RETURN_VALUE
>>>

设置函数转换列表的时间复杂度，反之亦然

Time complexity for function converting list to set and vice versa

python

big-o

time-complexity

python-3.x