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
Nguồn
2013-06-23 11:06:34
Tại sao bạn sử dụng 'N * N' trong vòng ngoài? Chỉ hiển thị 'c' sau khi kết thúc vòng lặp; sẽ cho bạn biết những gì bạn cần biết. –
sự phức tạp là BigO (N^3) –
@Tudor Vintilescu Bạn có thể giải thích lý do của bạn đằng sau điều này không? – RobotRock