algorithm - 这个算法的 big-O 代价函数是什么？

您如何用大 O 表示法描述以下内容？

rotors = [1,2,3,4,5 ...]
widgets = ['a', 'b', 'c', 'd', 'e' ...]

assert len(rotors) == len(widgets)

for r in rotors:
    for w in widgets:
        ...

    del widgets[0]

最佳答案

它是 O(n^2)。可以看到内循环执行次数为:

n + (n - 1) + (n - 2) + ... + 1

因为每次外循环迭代都会删除一个小部件。即 (n^2+n)/2，也就是 O(n^2)。