如何使用简单的步骤计算循环算法的时间复杂性

Question

我有以下代码，我完全迷失了这个循环结构的时间复杂性。实际上，它来自QuickSort，我读到这种循环结构具有复杂性O（n），但我无法理解。实际上，我不理解如何专门计算循环的复杂性，而循环除了简单的增量或减少条件以外，还满足了一些真正的错误条件。

while (i <= j) {
        while (array[i] < somevalue)
              i++;
        while (array[j] > somevalue)
              j--;
        if (i <= j) {
             #do something
              i++;
              j--;
        }
  };

Answer 1

此循环的复杂性大约是 #do something的次数。

在最坏的情况下，在任何迭代中，array[i] < somevalue和array[j] < somevalue都不是正确的。然后，#do something将被称为N/2次（以一种或另一种方式圆形 - 在这种情况下无关紧要），假设我们进入循环时i+j = N。

是 N/2，因为我们同时描述上下并增加下限，本质上是大小2的步骤。

因此，时间复杂性是O(N/2)，与O(N)相同。

Answer 2

O(N)，因为 i+j = N的价值相遇或彼此交叉时。

一旦i和j最终以(i <= j)变为false的方式，循环断开。

i ->                               <- j
<------------------N------------------->