python - Python - 列表中 O(n^2) 跳转次数的复杂性

Question

如果一个列表有 3 个元素，那么 O(n^2) 意味着我们必须进行 9 次跳转来导航 3 个元素的集合吗？如果一个跳跃只是一个元素，怎么可能是 9 次跳跃？

list = [1, 2, 3]

我不明白作者的意思是我们必须进行 9 次跳跃。有人可以解释一下吗？

标签： pythonlisttime-complexity

Answer 1

下面提供的代码示例是O(n)因为它使用 for 循环来迭代n元素。

n = len(list) # n = the length of the list here 3.
for i in range(0, n): # This runs n = 3 times, where n is the size of the list O(n)
    print(i)

现在考虑一个嵌套的 for 循环，这意味着您当前的 for 循环中的第二个循环。这是O(n^2)由于迭代n*n元素。

n = len(list) # n = the length of the list here 3.
for i in range(0, n): # This runs n = 3 times.
   for j in range (0, n): # This runs n = 3 times for each value of the i.
       print(j)

可以这样想，上面的代码段0, 1, 2在内循环中打印的次数与外循环指定的次数一样，在这种情况下为 3。因此，最后0, 1, 2, 0, 1, 2, 0, 1, 2将打印正好n*n= 3*3=9元素。