Big-O phức tạp của lồng cho vòng

Question

Tôi đang bối rối về sự phức tạp trong các cách sau (các hoạt động thực hiện bên trong vòng lặp bên trong là trong thời gian liên tục):

for(int i=0; i<n; i++) 
    for(int j=i; j<n; j++) 

là O này (n^2) hoặc O (n)? Tôi tìm O (n^2). Bất kỳ ý tưởng?

cũng sau đây làm cho tôi tò mò:

for(int i=0; i<n; i++) 
    for(j=0; j<i; j++) 

Answer 1

Chắc chắn O(n squared), tất nhiên. Giải thích tóm tắt cho cả hai trường hợp: 1 + 2 + ... + n là n(n+1)/2, nghĩa là, (n squared plus n)/2 (và trong Big-O chúng tôi thả phần thứ hai, nhỏ hơn, vì vậy chúng tôi sẽ để lại với n bình phương/2 mà tất nhiên là O(n squared)).

Answer 2

Bạn chính xác, các vòng lồng nhau đó vẫn là O (n^2). Số lượng hoạt động thực tế là một cái gì đó gần (n^2)/2, trong đó, sau khi loại bỏ các yếu tố 1/2 liên tục, là O (n^2).