为什么这个卡特彼勒算法O(n ^ 2)不是O(n ^ 3)？

Question

有人可以解释为什么这个算法O(n^2)？根据这个,它是O(n ^ 2).我认为它是O(n ^ 3)的原因是因为外部循环(对于x)运行n时间,内部循环(对于y)运行n-1时间,并且在最坏的情况下,例如A = [8, 100, 101, 102, 103, 104, 105, 106, 107],while循环(对于z)将运行n-2时间因此整体O(n^3).

为了完整性,A是一个带有正元素的排序数组,三元组(x,y,z)是一个三角形if A[x] + A[y] > A[z].找出可以从A构建多少个三角形.

        int TrianglesCount(int[] A)
        {
            int result = 0;
            for (int x = 0; x < A.Length; x++)
            {
                int z = x + 2;
                for (int y = x + 1; y < A.Length; y++)
                {
                    while (z < A.Length && A[x] + A[y] > A[z])
                        z++;
                    result += z - y - 1;
                }
            }
            return result;
        }

Answer 1

让我们仔细看看下面的代码片段

int z = x + 2;
for (int y = x + 1; y < A.Length; y++)
{
   while (z < A.Length && A[x] + A[y] > A[z])
      z++;
   result += z - y - 1;
}

for循环显然执行了A.lenght - (x+1)次数，也就是O(n)。然而，内部 while 循环A.length - (x+2)总共执行了最多次数，因为每次这样的执行都会递增 的值z，并且它可以递增最多A.length - (x+2)次数，直到 while 条件失败。再说一次，这最多是O(n)。因此，该片段的总时间复杂度可以被限制为O(n) + O(n) = O(n)。

O(n)由于代码片段针对的每个值运行x，因此总体时间复杂度为O(n^2)。

KMP算法中也使用了类似的思想来进行字符串匹配。