python - 在 python 脚本中测量复杂性的问题

Question

我在使用 Python 测量复杂性时遇到了问题。给出接下来的两个脚本:

1 def program1(L):              
2 multiples = []                
3 for x in L:                   
4     for y in L:               
5         multiples.append(x*y) 
6 return multiples        



1 def program3(L1, L2):
2 intersection = []
3 for elt in L1:
4     if elt in L2:
5         intersection.append(elt)
6 return intersection

在第一个最好的情况下(运行 sript 的最少步骤)是两个考虑空列表 L 所以只执行第二行和第六行。最佳情况的解决方案:2。

在最坏的情况下 L 是一个长列表，它在 L n 中遍历 x 的循环> 次。

内部循环有三个操作(给y赋值，x*y，和列表追加)。所以内层循环在外层循环的每次迭代中执行 3*n 次。因此，嵌套循环结构被执行 n * (3*n + 1) = 3*n**2 + n 次。添加第二行和第六行，我们得到解决方案 3n²+n+2。

但我的问题是:n(3n+1) 中的数字 1 是从哪里来的？

根据我的说法，解决方案是 n(3n)+2 = 3n²+2 vs 正确答案 n(3n+1)+2 = 3n²+n+2.

同时在第二个中，最坏的情况是 n²+2n+2 但我不明白如果只有一个循环，为什么会有二次项。

Answer 1

根据您的说法，y 的最内层( program1 )循环中有三个指令.

1. 分配给 y。
2. 计算 x*y。
3. 附加到列表。

按照同样的逻辑，最外层 ( x ) 循环中有一条指令:

1. 分配给 x。
2. 执行最里面的循环，见上文。

这将使外循环:

n * (1 {assign to x} + n * 3 {assign, multiply, append})

或者:

n * (1 + 3n)

添加 init/return 指令给出:

2 + n + 3n²

在program2 ，有一个类似的情况有一个“隐藏循环”:

2 instructions for init/return, plus ...

然后你运行for elt in L1 ，这将是 n迭代(n 是 L1 的大小)。您的内部代码是 if陈述。在最坏的情况下，if 主体总是运行。在最好的情况下，它永远不会运行。

if条件正在测试 elt in L2 ，它将运行一个迭代函数，type(L2).__contains__()在 L2 上。简单的情况是一个 O(m) 操作，其中 m是L2的长度。有可能 L2不是一个列表，而是某种类型，其中 in操作不需要线性扫描。例如，它可能是 B 树、字典、集合，或者谁知道是什么？所以你可以假设最好的情况是 elt in L2是O(1)，答案是否定的，而最坏的情况是elt in L2是 O(m)，答案是肯定的。

Best case:  2 + n * (1 {assign to elt} + 1 {search L2})
Best case if L2 is a list: 2 + n * (1 {assign to elt} + m {search L2})
Worst case: 2 + n * (1 {assign to elt} + m {search L2} + 1 {append})

这给你 2 + 2n 最好的情况，2 + n + nm 如果 L2 是一个列表，最好的情况是 2 + 2n + nm 最坏的情况。

您可能倾向于对待m等于n .那是你的决定，但如果你计算赋值语句，我会反对它。