最坏情况下采取的步骤数
No of steps taken in worst case
def program2(L):
squares = []
for x in L:
for y in L:
if x == y:
squares.append(x*y)
return squares
根据我的说法，在最坏的情况下采取的步骤数是 4*n^2 + 2 但这个问题的答案是 4*n^2 + 2 + n 并且解释如下
在最坏的情况下，L 是一个重复数字的长列表（即 [2, 2, 2, 2, ...]）。在这种情况下，我们通过循环 x in L n 次。每次通过这个循环，我们对变量 x 执行一次赋值，然后我们执行内部循环 for y in L n 次。
内部循环对变量 y 执行一次赋值。然后每次都会检查一个操作（如果 x == y）。由于最坏的情况是列表由相同的元素组成，因此此检查始终为真 - 因此始终执行第三个和第四个操作（x*y 和列表附加）。所以内循环在外循环的每次迭代中执行 4*n 次。因此嵌套循环结构被执行 n * (4*n + 1) = 4*n**2 + n 次！
添加两个步骤（对于第一个赋值语句和 return 语句）我们看到在最坏的情况下，该程序执行 4*n**2 + n + 2 个步骤。
为什么我们要加 + 1 (4n + 1)。无法理解这一点，因为没有执行的步骤是 4n（包括内部循环并且其中没有步骤）。
对于内循环：
(4*n+1) 部分包括：
4*n -> 也就是说，每个 y 变量一次。
- 正在为变量 y 赋值。
- 检查是否
x==y
- 正在计算
x*y。
- 将值附加到
squares
+1部分指的是内循环x的赋值，做了n次
然后，在最后，添加已经提到的其余两个步骤：声明 squares 并返回它。
def program2(L):
squares = []
for x in L:
for y in L:
if x == y:
squares.append(x*y)
return squares
根据我的说法，在最坏的情况下采取的步骤数是 4*n^2 + 2 但这个问题的答案是 4*n^2 + 2 + n 并且解释如下
在最坏的情况下，L 是一个重复数字的长列表（即 [2, 2, 2, 2, ...]）。在这种情况下，我们通过循环 x in L n 次。每次通过这个循环，我们对变量 x 执行一次赋值，然后我们执行内部循环 for y in L n 次。
内部循环对变量 y 执行一次赋值。然后每次都会检查一个操作（如果 x == y）。由于最坏的情况是列表由相同的元素组成，因此此检查始终为真 - 因此始终执行第三个和第四个操作（x*y 和列表附加）。所以内循环在外循环的每次迭代中执行 4*n 次。因此嵌套循环结构被执行 n * (4*n + 1) = 4*n**2 + n 次！
添加两个步骤（对于第一个赋值语句和 return 语句）我们看到在最坏的情况下，该程序执行 4*n**2 + n + 2 个步骤。
为什么我们要加 + 1 (4n + 1)。无法理解这一点，因为没有执行的步骤是 4n（包括内部循环并且其中没有步骤）。
对于内循环：
(4*n+1) 部分包括：
4*n -> 也就是说，每个 y 变量一次。
- 正在为变量 y 赋值。
- 检查是否
x==y - 正在计算
x*y。 - 将值附加到
squares
+1部分指的是内循环x的赋值，做了n次
然后，在最后，添加已经提到的其余两个步骤：声明 squares 并返回它。