c++ - 三和算法的时间复杂度是多少

Question

在数组中查找三个和为零的数的函数。

//helper function
bool isPresent(int*arr, int size, int index, int num)
{
    for (int i = index; i < size; i++)
    {
        if (arr[i] == num)
            return true;
    }
    return false;
}
bool threesum(int*arr,int size)
{
    int i = 0, j = 1;
    int sum = arr[i] + arr[j];
    while (i < size-2)
    {
        if (isPresent(arr, size, j + 1, -sum) == true)
        {
            cout << arr[i] << " + " << arr[j] << " + " << -sum << '\n';
            return true;
        }
        if (j == size)
        {
            i++;
            j = i + 1;
        }
        j++;
        sum = arr[i] + arr[j];
    }
    return false;
}

threeSum 函数中有两个循环，其中一个循环达到数组大小第二个是isPresent，它的时间复杂度是O(n) 所以threesum 函数的时间复杂度应该是O(n^2) 但是while 循环因为j 迭代了更多的时间，所以threesum 函数的时间复杂度是O(n^2) 2) 或 O(n^3)？

Answer 1

它是 O(n^3)。想想我是如何随着 j 改变的。假设，n = 10。一开始 i = 0，j = 1。我不会变成 1，直到 j = 10，然后在这些步骤之后，再次 i = 1，j = 2。就像写两个 for 循环一样这个:

for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)