元组中切片和星号组合的Python复杂度

Question

下面这个例子的复杂度是多少:

tuple_ = (1,2,..,3,1) # tuple of length n
(*tuple_[:k], *tuple_[k+1:]) # deleting element at index k

正常情况下，tuple_[:k]和tuple_[k+1:]的切片分别为O(k)和O(n-k)。但是切片首先发生，然后元素一个接一个地添加到结果元组意味着另一个n操作?我知道复杂度是O(2n)就是O(n)但我想知道操作的次数是否因为星号而翻倍了?

Answer 1

假设我们有一个输入:

tuple_ = tuple(range(1000))
k = 400

让我们用dis模块分析两个表达式:(tuple_[:k], tuple_[k+1:])和(*tuple_[:k], *tuple_[k+1:])，以发现并比较在下执行了哪些重要操作。

表达式# 1:

import dis
...
dis.dis("(tuple_[:k], tuple_[k+1:])")

---

1           0 LOAD_NAME                0 (tuple_)
2 LOAD_CONST               0 (None)
4 LOAD_NAME                1 (k)
6 BUILD_SLICE              2
8 BINARY_SUBSCR
10 LOAD_NAME                0 (tuple_)
12 LOAD_NAME                1 (k)
14 LOAD_CONST               1 (1)
16 BINARY_ADD
18 LOAD_CONST               0 (None)
20 BUILD_SLICE              2
22 BINARY_SUBSCR
24 BUILD_TUPLE              2
26 RETURN_VALUE

这里的重要操作是BUILD_SLICE1,BUILD_SLICE2和BUILD_TUPLE，它们将表达式的运行时间加起来为O(k)+O(n - (k + 1))+O(2)(作为最终元组BUILD_TUPLE只包含2片/元组)。

---

表达式# 2:

dis.dis("(*tuple_[:k], *tuple_[k+1:])")

---

1           0 BUILD_LIST               0
2 LOAD_NAME                0 (tuple_)
4 LOAD_CONST               0 (None)
6 LOAD_NAME                1 (k)
8 BUILD_SLICE              2
10 BINARY_SUBSCR
12 LIST_EXTEND              1
14 LOAD_NAME                0 (tuple_)
16 LOAD_NAME                1 (k)
18 LOAD_CONST               1 (1)
20 BINARY_ADD
22 LOAD_CONST               0 (None)
24 BUILD_SLICE              2
26 BINARY_SUBSCR
28 LIST_EXTEND              1
30 LIST_TO_TUPLE
32 RETURN_VALUE

这里Python从BUILD_LIST开始构建一个空列表。有几个原因:1)拆包需要变平一个序列;2)并非所有的参数都需要解包，因此可以将扁平化安排在最终容器的不同点上。因为tuple是不可变的，所以list被用作内部存储。

这里的重要操作是BUILD_SLICE1,LIST_EXTEND1,BUILD_SLICE2,LIST_EXTEND2和LIST_TO_TUPLE。它们将表达式的运行时间汇总为O(2k)+O(2(n - (k + 1)))+O(n)

这种复杂性似乎很有代表性。