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

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

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

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

因为你要通过两个循环,它是O(n^2)。

因为断言:

assert len(rotors) == len(widgets)

O(n)的答案 ^二 )是正确的,但在一般情况下,如果列表的长度不一定相同,您可以将其称为O(m*n)。

该算法的性能最差为O(n^2)。

是O(n^2),但我认为人们缺少此问题的“删除”部分。

The first loop you have n widgets.
The second loop you have n-1 widgets.
...
The n-1 loop you have 2 widgets.
The n loop you have 1 widgets.

你可能认为你降低了big-o,但是所有的删除操作都是将系数乘以1/2。

这是因为n+(n-1)+…+2+1=n(n+1)/2。当n变为无穷大时,它变为n^2/2,即0(n^2)

冒着相反和学究的风险,你真的没有提供足够的信息来回答一般的问题。当然,性能并不比O(n^2)好,但是由于您没有给出关于您在内部循环中所做的事情的详细信息,所以通常情况下会更糟。但是,假设内部循环中的情况是O(1),那么总体性能是O(n^2)。

是的,这就是为什么这些大问题总是很难解决的原因。 但如果我不得不猜的话,我会说O(n^2),因为你每次都要通过2个循环来执行一些操作。