半尺寸嵌套循环的时间复杂度

Question

void function(int n)
{
    int count = 0;

    // outer loop 
    for (int i=n/2; i<=n; i++)

        // middle loop 
        for (int j=1; j+n/2<=n; j = j++)

            // inner loop executes log n times
            for (int k=1; k<=n; k = k * 2)
                count++;
}

我正在做一些练习，有人可以帮我找出上面算法的Big-Oh吗？我知道最里面的循环执行了 log n 次。最外面的循环和中间的循环呢？那也会是 log n 或 n/2 吗？

Answer 1

假设完整缩进的代码是这样的：

void function(int n)
{
int count = 0;

// outer loop 
for (int i=n/2; i<=n; i++){

    // middle loop 
    for (int j=1; j+n/2<=n; j++){
        // inner loop executes log n times
        for (int k=1; k<=n; k = k * 2){
            count++;
        }
    }
 }
}

时间复杂度可以这样计算：

最里面的循环执行了(log n)次，所以它的复杂度是O(log n).
以j为循环变量的中间循环执行n / 2次，最内层循环执行，每次都在其迭代中。因此，中间循环的时间复杂度为(n / 2) * O(log n) = O(n * log n)。
同样，最外层的循环也执行了(n / 2)次，中间的循环每次迭代都在其中完整执行。因此，它的时间复杂度将是 (n / 2) * O(n * log n) = O(n * n * log n).

因此，整体时间复杂度将是 O(n^2 * log n)。

半尺寸嵌套循环的时间复杂度

Time Complexity for nested loops with half-size

big-o

time-complexity

nested-loops