一本入门教材给出了以下函数作为多项式复杂度的例子:
def intersect(L1, L2):
"""
Assumes L1 and L2 are lists
Returns a list without duplicates that is intersection of L1 and L2
"""
# Part i - Build a list containing common elements
tmp = []
for e1 in L1:
for e2 in L2:
if e1 == e2:
tmp.append(e1)
break
# Part ii - Build a list without duplicates
result = []
for e in tmp:
if e not in result:
result.append(e)
return result
- 作者说部分(i)的运行时间为
Θ(len(L1)*len(L2))阶，但这似乎意味着部分(i)在所有情况下运行在Θ(len(L1)*len(L2))阶，这是正确的吗?
当我试着完成这个例子时，在最坏和最好的情况下，我得到了不同的运行时间:
- 最坏:L1的所有元素都与L2的最后一个元素匹配==>
Θ(len(L1)*len(L2))。 最好 - :L1的所有元素都与L2的第一个元素匹配==>
Θ(len(L1))。
…所以我会说(I)部分是最坏情况下的Θ(len(L1)*len(L2))订单。
- 作者然后说，部分(ii)不是
Θ(len(tmp))，而是Θ(len(tmp)*len(result))，因为e not in result可能要求我们检查result中的所有元素，这将在Θ(len(result))中运行。但由于len(result)和len(tmp)被len(L1)和len(L2)中较小的一个所限制，所以Θ(len(tmp)*len(result))可以忽略。
我明白Θ(len(tmp)*len(result))是一个附加术语，因此可以忽略，但我再次不确定为什么作者对第(ii)部分做了一个笼统的陈述——他们是说第(ii)部分在所有情况下都是Θ(len(tmp)*len(result))吗?
由于部分(ii)中的循环取决于部分(i)中的循环的输出，因此我认为result在最坏情况下的长度为1(正如我在上面定义的那样)，因此部分(ii)的最坏情况运行时间将是Θ(len(tmp))阶，而不是Θ(len(tmp)*len(result))阶。这似乎是错误的，但我不确定如何描述这种循环。
我对这个话题不熟悉，所以任何指导都将非常感激。
编辑:同样的段落在书的旧版本中使用Big-O代替Big-Theta。
作者说，部分(i)的运行时间是订单
Θ(len(L1)*len(L2))，但这似乎意味着部分(i)运行在Θ(len(L1)*len(L2))在所有情况下，这是正确的吗?
。作者使用Big Θ的意义在于他们在第三版(文本与第二版不同)的同一章第11.2节中进行了解释——注意使用了"最坏情况";我高亮显示了:
许多计算机科学家会滥用大O表示法，做出这样的陈述:"f(x)的复杂度是O(x²)。"他们的意思是在最坏的情况下f的运行不超过O(x²)步。[…]
[…我们将使用Big Theta(Θ)当我们描述的东西既是上界又是下界时关于渐近最坏情况运行时间。
那么你下面的想法也得到了解释:
…所以我会说(I)部分是订单
Θ(len(L1)*len(L2))在最坏情况下。
你现在就会明白这正是作者想说的。
由于第(ii)部分中的循环取决于第(i)部分中的循环的输出，因此我认为
result在最坏情况下的长度为1(如上所述)，因此第(ii)部分的最坏情况运行时间将是Θ(len(tmp))阶，而不是Θ(len(tmp)*len(result))阶。
你定义了a前面是最坏的情况，但是部分(i)中还有其他最坏的情况，在部分(ii)中也表现最差。
以L1具有𝑛唯一元素的情况为例，其中L2是L1的副本。
在part (i)中，内部循环第一次迭代一次，第二次迭代两次，…等。所以总的来说，内部循环是1+2+3+4+…+𝑛迭代。这对应于𝑛(𝑛+1)/2次迭代，即Θ(𝑛²)，这是最坏的情况。tmp将是L1的副本。
现在看第(ii)部分:if块将在每次迭代中执行，因为tmp没有重复项。in操作将扫描result中的所有值。在第一次迭代中，result将是空的，所以没有什么可扫描的，但在第二次迭代中，它将有1个元素，然后是2个元素，所以我们再次得到0+1+2+3…+(𝑛-1)步进in运算符Θ(𝑛²)。
你是对的。如果L1只包含重复的L2的第一个元素，则第一个循环将运行L1次，tmp的长度为L1。那么结果的长度将不超过1，并且最后一个循环的时间也为L1。
但这与书中的内容并不矛盾。