java - Big O for specific double for loop

Question

public void f7(int N) {
    for (int i = N / 2; i > 0; i--) {
        if (i % 2 == 0) {
            for (int j = 0; j < N; j += 2) {
                System.out.println("Hey");
            }
        } else {
            for (int j = 1; j < N; j *= 2) {
                System.out.println("You");
            }
        }
    }
}

所以我试图找到这个特定代码块的渐近复杂度(大 O)。

我的想法:第一个 for 循环是 O(N)，并且因为有一半时间数字是奇数而另一半时间是偶数，所以里面的 for 循环仍然是 O(N)由于 j *= 2，if 语句和 else 语句中 for 循环的 O(Log N)。所以对于我的最终答案，我得到了 O(N^2(Log N))，但显然答案只是O(N^2)。我想知道是否有人可以解释我的想法哪里出了问题？谢谢!

Answer 1

O(Log N) 内循环的运行时间只对 i 的奇数值是正确的(它们是 i 可能值的一半)。对于 i 的偶数值，内部循环的运行时间为 O(N)，因为 j 在每次迭代中递增 2 .

所以你拥有的是

(N/4 * N/2) + (N/4 * log(N)) 
  even i          odd i

是 O(N²)，因为第一项(渐近地是增长更快的项)是 N²/8，它渐近地是 O(N ²).