algorithm - 该算法的大 O 成本函数是什么？

Question

您如何用大 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]

Answer 1

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

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

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