这个算法的大O成本函数是什么？

Question

你如何用big-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).

Answer 2

因为你经历了两个循环,所以它是O(n ^ 2).