特定双循环的大O.

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");
            }
        }
    }
}

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

我的想法:第一个for循环是O(N),因为有一半的时间数字是奇数而另一半时间是偶数,所以if语句中的for循环仍然是O(N)因为j*= 2,所以在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 ²).