我是否正确计算了这些函数的 Big O？

Question

我试图找到以下两个函数的时间复杂度： 第一个

public static int myMethod1(int[] arr) {
    int x = 0;
    for (int i = 0; i < arr.length / 2; i++) {
        for (int j = 0; j < arr.length; j++) {
            for (int k = 0; k < arr.length; k++) {
                x++;
                if (k == arr.length / 2) {
                    break;
                }
            }
        }
    }
    return x;
}

所以我在想这个。 该方法包含 3 个循环，循环遍历变量 i、j 和 k…… i 和 j，以及 k 每次传递都递增 1...这给了我们 N 对于每个循环，给我们留下了三个 N..，它给出了 O(N^3)

下一个是：

public static int myMethod(int N) {
    int x = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N / 2; j++) {
            for (int k = 1; k < N;) {
                x++;
                k *= 2;
            }
        }
    }
    return x;
}

有了这个我在想。 该方法包含 3 个循环，循环在变量 i、j 和 k 上迭代……每次传递 i 和 j 都递增 1……这给了我们 N 对于每个循环，这给我们留下了两个 N。最后一个循环k 加倍，给出的是 log(n)。 因此这个问题的结果是 O(N^2· log (N))

这是正确的吗？如果不是，为什么？

Answer 1

你是对的。在这两个问题中