phân tích tiệm cận của ba lồng cho vòng

Question

tôi muốn để tính toán mức độ phức tạp của theta lồng nhau này cho vòng lặp:

for (int i = 0; i < n; i++) { 
     for (int j = 0; j < i; j++) { 
      for (int k = 0; k < j; k++) { 
       // statement 

tôi muốn nói đó là n^3, nhưng tôi không nghĩ rằng điều này là đúng, bởi vì mỗi vòng lặp không đi từ 1 đến n. Tôi đã làm một số xét nghiệm:

n = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

Vì vậy, nó phải nằm giữa n^2 và n^3. Tôi đã thử công thức tổng kết và như vậy, nhưng kết quả của tôi là quá cao. Mặc dù n^2 log (n), nhưng điều đó cũng sai ...

Answer 1

Đó là O(N^3). Công thức chính xác là (N*(N+1)*(N+2))/6

Answer 2

Sử dụng Sigma Notation là một bước hiệu quả bằng phương pháp bước: