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

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，两者都可以在内循环中增长，因此复杂度应该低于n，但是log（n）基本上只是一个猜测。

任何人都可以帮助我了解，如何以正确的方式解决这个问题？

编辑：如注释中所指出，将r=0更改为r=n-1。我的坏。

Answer 1

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

[看一下-左索引仅向右移动，右索引仅向左移动，并且循环起作用直到它们相遇。

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