algorithm - 嵌套循环中的步骤数

Question

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

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

我的计算方式如下(列表由大量元素组成 = "n"):

1. 赋值语句(步骤数 = 1):

   multiple = []

2. 嵌套循环:

   for o in list:
      for i in list:
          multiple.append(o*i)
   

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

3. 返回语句(步骤数 = 1):

   return multiple

因此总数没有。步骤数 = 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