algorithm - 两个嵌套 for 循环的复杂性，其中内部循环变得更短？

Question

我正在按特定顺序按元素的值从数组中提取元素，但无法找到正确的 O() 运行时(或任何其他运行时)。

代码可以表示如下:

while (not arr.isEmpty()):
    for (n : arr):    
         //Do stuff
         remove arr[n]

但我一直无法说出实际功能会是什么样子。

Answer 1

总和应该只是 (m-j) 的总和，没有 m*。您可以将此总和计算为 m(m+1)/2，这表明工作量为 O(m^2)。