嵌套循环中的步骤数

Question

我正在尝试计算为以下专门用于渐近增长的嵌套循环执行的步骤数。根据步数，我将推导出该算法的大 O。

def get_multiples(list):
    multiple = []
    for o in list:
        for i in list:
            multiple.append(o*i)
    return multiple

我的计算方式如下（列表由大量元素组成="n"）：

赋值语句（步数=1）：
```
multiple = []
```

嵌套循环：

for o in list:
   for i in list:
       multiple.append(o*i)
</pre>

在外层循环中，变量o被赋值了n次。每次执行外层循环时，首先为变量 i 赋值 n 次，然后将变量相乘 n 次，最后将列表追加 n 次。因此没有。步骤数 = n*(n+n+n) = 3n²

Return 语句（步骤数 = 1）：
```
return multiple</pre>
```

所以总数没有。步骤数 = 3n² + 2

然而正确答案是3n² + n +2。显然，外循环的执行需要额外的 n 步，而内循环不需要这些步骤。

有人可以向我解释我错过了什么吗？

它对复杂性没有影响，因为它仍然是 O(n²)

Answer 1

我认为计算嵌套循环的正确方法如下：

号码o被分配了n次。数字i被赋值n²次，o*i被计算n²次，append函数被调用n²次。

因此 n + n² + n² + n² = 3n² + n

将它添加到其余部分，你得到 3n² + n + 2

Answer 2

def get_multiples(list):  
  multiple = []  // 1 STEP  
  for o in list:  // Executed n times, so n STEPS  
    for i in list: // Executed n times for each value of o, so n*n STEPS  
      multiple.append(o*i) // 1 STEP to multiply and 1 STEP to append, repeated for each pair of (o, i), so 2*n*n STEPS  
  return multiple // 1 STEP

加上以上：1 + n + n² + 2n² + 1 = 3n² + n + 2

嵌套循环中的步骤数

Number of steps in a nested loop

algorithm

big-o

time-complexity