分析下面代码的复杂度

Question

分析下面代码的复杂度
分析下面代码的复杂度
分析下面代码的复杂度

Answer 1

该回答引用自GPT-4o，由博主小ᶻZ࿆编写：

分析下面代码的复杂度

1. 第一段代码

void func(int n) {
    int i, j, k, count = 0;
    for (i = n / 2; i <= n; i++) 
        for (j = 1; j <= n; j = j * 2) 
            for (k = 1; k <= n; k = k * 2) 
                count++;
}

复杂度分析：
第一层循环：i 从 n/2 到 n，运行了 n/2 次，时间复杂度为 O(n)。
第二层循环：j 从 1 以 2 的倍数递增，即每次翻倍，执行次数为 log(n)，时间复杂度为 O(log n)。
第三层循环：k 与 j 类似，也是以 2 的倍数递增，执行次数为 log(n)，时间复杂度为 O(log n)。
总体时间复杂度为：O(n * log(n) * log(n)) = O(n * log^2(n))。

function(int n) {
    if (n == 1) return;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            print("*");
            break;
        }
    }
}

2. 第二段代码：

function(int n) {
    if (n == 1) return;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            print("*");
            break;
        }
    }
}

复杂度分析：

• 第一层循环：i 从 1 到 n，执行了 n 次，时间复杂度为 O(n)。
• 第二层循环：j 从 1 到 n，但由于 break 的存在，只执行一次，时间复杂度为 O(1)。
  总体时间复杂度为：O(n)。

3. 第三段代码

void func(int n) {
    int i = 1, j = 0;
    while (i + j <= n) {
        if (i > j) 
            j++;
        else 
            i++;
    }
}

复杂度分析：
每次循环中，i 或 j 都会增大，因此每次循环的执行次数大约是 n 次。
总体时间复杂度为：O(n)。

总结：

• 第一段代码的时间复杂度为 O(n * log^2(n))。
• 第二段代码的时间复杂度为 O(n)。
• 第三段代码的时间复杂度为 O(n)。

如有帮助，题主可以采纳一下嘛，谢谢~