java - 内循环与n/2外循环的算法分析关系

Question

我无法计算这段代码的时间复杂度:

public static void myfun1 (int n) {
    System.out.println("n = " + n);
    for (int k = 1; k <= n / 2; k++){
        System.out.println(k);
        for(int m = 1; m <= k; m++){
            System.out.println(k + ", " + m);
        }
    }
 }
public static void main(String[] args){
    myfun1(8);
}

当我运行 n=8 时，输出如下:

我认为第一个循环将运行 (n/2)，我必须将它乘以内部循环。我遇到的麻烦是内循环。通常我会假设两个嵌套循环是 (n^2) 但我觉得第一个循环中的 n/2 是正确的但我不确定内部循环如何与它相关。我从每个 k 的输出中看到我的 m 完成了 k 次循环。出于某种原因，我的大脑无法根据 n 来翻译这种关系。有人可以给我一些指导吗？ 提前致谢。

Answer 1

您的内部循环第一次运行 1 次 第二次 2 次...最多 n/2

所以它的运行方式类似于从 1 到 n/2 = ((n/2+1)*n)/4

的整数之和

(对于8，运行10次，加个计数器确定)

所以这里的复杂度是 O(n**2)。