如何找到这段代码的时间复杂度？

Question

 sort(S);
 for i=0 to n-2 do
    a = S[i];
    start = i+1;
    end = n-1;
    while (start < end) do
       b = S[start]
       c = S[end];
       if (a+b+c == 0) then
          output a, b, c;
          start = start + 1;
          end = end - 1;
       else if (a+b+c > 0) then
          end = end - 1;
       else
          start = start + 1;
    end
 end

Answer 1

让我们通过考虑最坏的情况来简化伪代码。

 sort(S); # O(N log(N))

 for i=0 to n-2 do # O(N)

    start = i+1; # O(1)
    end = n-1; # O(1)

    while (start < end) # O(N - i)
       start = start + 1;  # O(1)
    end
 end

也可以写成：

 sort(S); 

 for i=0 to n-2 do 
    for j = i+1 to n-1 do:
       ...
    end
 end

因此迭代次数为

1/2 N * (N+1) = O(N^2)