下面这个例子的复杂性是什么？
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），但我想知道操作的数量是否因为星号而加倍？
下面这个例子的复杂性是什么？
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），但我想知道操作的数量是否因为星号而加倍？
1条答案
按热度按时间vfh0ocws1#
假设我们有一个输入：
我们来分析两个表达式：
(tuple_[:k], tuple_[k+1:])和(*tuple_[:k], *tuple_[k+1:])，使用dis模块来发现和比较 * 在幕后 * 执行了哪些重要操作。表达式#1：
这里重要的操作是
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:])")这里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)**复杂性似乎很有代表性。