確定特定循環的大（O）效率

Question

我被要求確定此循環的大O符號。

int x = 1; 
    int n = 1000; 
    while (x < (n*n)) 
    { 
     int y = n; 
     while (y > 0) 
     { 
      y = y-1; 
     } 
     x = x+x; 
    } 

現在我看到的是一個嵌套循環。但這絕對不是N^2，對嗎？ 我明白什麼使O（n）或O（log（n））成爲某事物，但我將如何去確定一個特定的循環，比如這個？

Answer 1

內環運行從Ñ到，所以它是爲O（n）。

外環

while (x < (n*n)) { 
    ... 
    x = 2*x; 
} 

是對數的，從到N * N，這將是O（的log（n ））= O（2爲log N運行）= O（log n）。

由於循環嵌套時，你乘的複雜性得到爲O（n log n）的。