具有嵌套循环的函数的时间复杂度

Question

我正在尝试了解如何确定 big-O，我已经找到了这个算法，但我不太确定我用这个算法进行的计算。

Compute(A,n,x):
begin
  l=0;
  r=n-1;
  while true do
     while l<r and A[l] < x do
         l=l+1;
     end
     while l<r and A[r] >= x do
         r=r-1;
     end
     if l>=r then
        return
     end
     tmp = A[l];
     A[l]=A[r];
     A[r]=tmp;
     l=l+1;
     r=r-1;
  end
end

我的猜测是 O(n*log(n))，但没有任何正确的理由。我当时的想法...

内部循环都有 O(n)，所以我可以添加这两个，仍然有 O(n)。而外层循环会根据l,r结束，l,r都可以在内层循环增长，所以复杂度应该低于n，但是log(n)基本上只是一个猜猜

谁能帮我理解，如何以正确的方式处理这个问题？

编辑：正如评论中指出的那样，将 r=0 更改为 r=n-1。我的错。

Answer 1

如果您将 r 的初始值更改为 n-1（似乎这是一个愚蠢的错误），您将得到类似于 Hoare 分区（Quicksort 算法的一部分）的 O(n) 过程。

看看 - 左索引只向右移动，右索引只向左移动，循环工作直到它们相遇。

r=0; 没有意义 - 例程立即停止

具有嵌套循环的函数的时间复杂度

Time complexity of function with nested loops

algorithm

big-o

time-complexity