时间戳

首页 > 解决方案 > 半尺寸嵌套循环的时间复杂度

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

问题描述

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 ？

标签： time-complexitybig-onested-loops

解决方案

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

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++;
        }
    }
 }
}

时间复杂度可以计算如下：

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

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

推荐阅读