c++ - 带有嵌套 if-else 的循环的时间复杂度

Question

// Every iteration of loop counts triplet with 
// first element as arr[i]. 
for (int i = 0; i < n - 2; i++) { 

    // Initialize other two elements as corner 
    // elements of subarray arr[j+1..k] 
    int j = i + 1, k = n - 1; 

    // Use Meet in the Middle concept 
    while (j < k) { 

        // If sum of current triplet is more or equal, 
        // move right corner to look for smaller values 
        if (arr[i] + arr[j] + arr[k] >= sum) 
            k--; 

        // Else move left corner 
        else { 

            // This is important. For current i and j, 
            // there are total k-j third elements. 
            for (int x = j + 1; x <= k; x++) 
                cout << arr[i] << ", " << arr[j] 
                     << ", " << arr[x] << endl; 
            j++; 
        } 
    } 
} 

这个算法的时间复杂度是多少？是 O(n*n) 吗？这是 geekforgeeeks 网页的问题。如何处理 else 语句中的循环？

Answer 1

将代码分成几部分并找出每个部分的运行时间。

外层的 for 循环是 O(n)。

每次调用该循环时，都会调用一个 while 循环。因此，您将成倍增加两个循环的复杂性。

要弄清楚 while 循环的运行时间，您必须查看 if 和 else block 。如果 if block 每次都运行，那么 while 循环的复杂度为 O(n)。如果 else 部分每次都运行，那么 while 循环的复杂度为 O(n^2)。

如果我们考虑最坏的情况，那么您将忽略 if block 运行时。因此，while 循环运行时间为 O(n^2)，并且通过外部 for 循环调用了 n 次。

因此，这一切的运行时间应该是 O(n^3)。