Độ phức tạp thời gian Big-O của các vòng lặp lồng nhau sau đây:Big-O của vòng lặp lồng nhau là gì, trong đó số lần lặp trong vòng lặp bên trong được xác định bởi vòng lặp hiện tại của vòng lặp bên ngoài?
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
System.out.println("i = " + i + " j = " + j);
}
}
Sẽ là O (N^2)?
Đúng, nó vẫn là O (n^2), nó có hệ số không đổi nhỏ hơn, nhưng điều đó không ảnh hưởng đến ký hiệu O.
Có, nó sẽ là N bình phương. Số bước thực tế sẽ là tổng của 1 đến N, là .5 * (N - 1)^2, nếu tôi không nhầm. Big O chỉ tính đến phụ âm cao nhất và không có hằng số, và do đó, đây vẫn là N bình phương.
Bạn chỉ cần tắt một chút - tổng số từ 1 đến n là n * (n + 1)/2 hoặc .5 * n^2 + .5 * n, rõ ràng là O (n^2). – user57368
Có. Nhớ lại định nghĩa của Big-O: O (f (n)) theo định nghĩa nói rằng thời gian chạy T (n) ≤kf (n) đối với một số liên tục k. Trong trường hợp này, số lượng các bước sẽ là (n-1) + (n-2) + ... + 0, sắp xếp lại thành tổng 0 đến n-1; đây là
T (n) = (n-1) ((n-1) +1)/2.
Sắp xếp lại và bạn có thể thấy rằng T (n) sẽ luôn là ≤ 1/2 (n ²); theo định nghĩa, do đó T (n) = O (n ²).
Đó là N bình phương nếu bạn bỏ qua System.out.println. Nếu bạn giả định rằng thời gian thực hiện bằng cách đó sẽ là tuyến tính trong đầu ra của nó (mà nó cũng có thể không được, tất nhiên), tôi nghi ngờ bạn kết thúc với O ((N^2) * log N).
Tôi đề cập đến điều này không phải là cầu kỳ, nhưng chỉ để chỉ ra rằng bạn không chỉ cần đưa các vòng rõ ràng vào tài khoản khi làm việc ra phức tạp - bạn cần phải nhìn vào sự phức tạp của những gì bạn gọi là tốt.
Bạn nói nó ngầm, nhưng cần lưu ý rõ ràng rằng sự phức tạp phụ thuộc vào những gì bạn xem xét "đơn vị công việc". Nếu println là đơn vị công việc, thì đó là O (n^2), nếu lệnh máy là đơn vị công việc, thì nó giống như bạn nói. –
Nó khá kỳ quặc đối với đơn vị công việc phụ thuộc vào n mặc dù - hoặc ít nhất, nó làm cho nó ít hữu ích trong thế giới thực, IMO. –
Bạn có thể cho tôi biết T (n) là gì không? – CodyBugstein
Nếu bạn có N = 10, bạn lặp lại sẽ là: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (đây là: mười lần lặp cộng với chín lần lặp cộng với tám lần lặp ... vv).
Bây giờ, bạn cần phải tìm vào việc bổ sung bao nhiêu lần bạn có thể nhận được một N (10 trong ví dụ):
1: (10), 2: (9 + 1), 3: (8 +2), 4: (7 + 3), 5: (6 + 4). Đó là 5 lần ... và dựa trên 5 lần lặp lại.
Bây giờ bạn biết rằng bạn có năm hàng chục + 5:
10 (5) + 5
Về f (n) (hoặc N), chúng ta có thể dễ dàng nhận thấy rằng đây sẽ là:
f (n) = n (n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2 ... đây chính là độ phức tạp của những vòng lặp lồng nhau.
Nhưng, xem xét hành vi tiệm cận của Big O, chúng ta có thể loại bỏ các giá trị ít quan trọng hơn của f (n), là n và đơn vị mẫu.
Kết quả: O (n^2)
AFAIL, được bắt đầu từ vòng lặp bên trong thông qua những người bên ngoài là cách thích hợp để tính phức tạp vòng lặp lồng nhau. 
Xem thêm [Độ phức tạp thời gian của vòng lặp lồng nhau] (http://stackoverflow.com/q/526728/456814). –