Big O - Vòng lặp lồng nhau

Question

void bar(int N){ 
    int c=0; 
    for (int i=0; i<N*N; i++) 
    for (int j= i; j< N; j++) 
     c++; 
} 

Vòng ngoài (và bên trong) không bao giờ vượt qua N. Điều này có nghĩa Big O là N * N (N cho bên ngoài và N/2 cho bên trong)?

Answer 1

Nếu bạn làm điều này

for (int i = 0; i < N; i++) 
    for (int j = i; j < N; j++) 
    … 

bạn sẽ lặp N lần trong vòng lặp bên trong trước, sau đó N-1, sau đó N-2, vv, tóm tắt đến N (N-1)/2 . Vòng lặp này chạy trong O (N²), đó là hình vuông của vòng lặp bên ngoài.

Trong trường hợp của bạn, mã của bạn là tương đương với

for (int i = 0; i < N; i++) 
    for (int j = i; j < N; j++) 
    c++; 

vì đối với mỗi số nguyên dương ta có n ² ≥ N và trình biên dịch sẽ đủ thông minh để nhận thấy rằng nó làm cho không có ý nghĩa để tiếp tục chạy vòng ngoài nếu tôi lớn hơn N. Vậy độ phức tạp thực sự là O (N²).

Nếu bạn in N và c sau khi chương trình chạy, bạn sẽ nhận thấy rằng khi N được tăng gấp đôi, c hầu như nhân với 4 (2²):

N = 1, c = 1 
N = 2, c = 3 
N = 4, c = 10 
N = 8, c = 36 
N = 16, c = 136 
N = 32, c = 528 
N = 64, c = 2080 
N = 128, c = 8256 
N = 256, c = 32896 
N = 512, c = 131328 
N = 1024, c = 524800 
N = 2048, c = 2098176 

Answer 2

Để biết chính thức số lần lặp và thứ tự tăng trưởng: