Độ phức tạp của vòng lặp lồng nhau này cho vòng lặp ba là gì?

Question

Tôi đã tìm kiếm một chút trên StackOverflow và đã hiểu sự phức tạp lên đến điểm của vòng lặp j, là O(n2). Tuy nhiên với việc bổ sung lồng nhau của vòng lặp k, tôi nhầm lẫn là tại sao độ phức tạp trở thành O(n3). Ai đó có thể giúp tôi hiểu điều này không?

Từ hiểu biết của tôi, vòng lặp i có n lần lặp lại và vòng lặp j có 1 + 2 + 3 + ... + n lần lặp n*(n+1)/2 là O(n2).

for(i = 1; i < n; i++) { 
    for(j = i+1; j <= n; j++) { 
     for(k = i; k <= j; k++) { 
      // Do something here... 
     } 
    } 
} 

EDIT: Thanks for all guys giúp đỡ của bạn :) Balthazar, tôi đã viết một đoạn mã mà sẽ tăng quầy tùy thuộc vào vòng lặp họ đang ở, kinda một cách thô bước-by- bước:

#include <iostream> 

int main(int argc, const char * argv[]) 
{ 
    int n = 9; 
    int index_I = 0; 
    int index_J = 0; 
    int index_K = 0; 
    for (int i = 1; i < n; i++) { 
     for (int j = i+1; j <= n; j++) { 
      for (int k = i; k <= j; k++) { 
       index_K++; 
      } 
      index_J++; 
     } 
     index_I++; 
    } 
    std::cout << index_I << std::endl; 
    std::cout << index_J << std::endl; 
    std::cout << index_K << std::endl; 
    return 0; 
} 

tôi chạy mã này từ n = 2 n = 9 với gia số 1 và đã có các trình tự sau:

Từ các quầy, có thể thấy rằng: i = n-1 cho độ phức tạp của O (n) và j = ((n-1) * n)/2 cho độ phức tạp O(n2). Một mô hình cho K rất khó để phát hiện nhưng nó được biết rằng K phụ thuộc vào J, do đó:

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 đưa ra một phức tạp của O(n3)

Tôi hy vọng điều này sẽ giúp mọi người trong tương lai.

EDIT2: nhờ Dukeling cho các định dạng :) Cũng tìm thấy một sai lầm trong dòng cuối cùng, điều chỉnh tại

Answer 1

Hãy xem this dụ để đánh giá trường hợp phức tạp nhất. Về bản chất, nếu bạn đánh giá nó theo từng dòng, bạn sẽ nhận được một cái gì đó như O (n^3/C), trong đó C là một số hằng số, thường bỏ qua trong các đánh giá như vậy, dẫn đến O (n^3) .

Answer 2

k-loop có O (ji) phức tạp

j-loop có O ((ni) * (ni)) phức tạp

i-loop có O (n * n * n) = O (n^3) phức tạp

dù sao, bạn biết rằng nó không phải là O (n^2) vì hai vòng đầu tiên là O (n^2) và nó không quá O (n^3) bởi vì chỉ có 3 vòng

Answer 3

Điều này khá phức tạp để giải thích không có sơ đồ, nhưng mỗi vòng lặp lồng nhau sẽ lặp "n" số lần trước khi trả về lần lặp lại cho pa thuê.

Vì vậy, như jambono chỉ ra, mỗi vòng lặp lồng nhau yêu cầu so sánh/đánh giá cho mỗi lần lặp của "n". Vì vậy, "n" được so sánh với các biến cục bộ trong mỗi vòng lặp (n * n * n) làm cho O (n^3).

Bước mã trong trình gỡ lỗi để có chỉ báo trực quan về độ phức tạp của máy được xử lý như thế nào.

Answer 4

Nếu bạn đang quen với Sigma Notation, đây là một cách thức để suy ra độ phức tạp của thuật toán của bạn (các vòng lồng nhau đơn giản, chính xác):

NB: các công thức có thể đơn giản hóa chứa lỗi. Nếu bạn phát hiện bất cứ điều gì, xin vui lòng cho tôi biết.

Answer 5

Đầu tiên chúng ta sẽ xem xét các vòng lặp mà số lần lặp của vòng lặp bên trong không phụ thuộc vào giá trị của chỉ số vòng lặp bên ngoài. Ví dụ:

for (i = 0; i < N; i++) { 
     for (j = 0; j < M; j++) { 
      sequence of statements 
     } 
    } 

Vòng lặp bên ngoài thực thi N lần. Mỗi khi vòng lặp bên ngoài thực hiện, vòng lặp bên trong thực thi M lần. Kết quả là, các câu lệnh trong vòng lặp bên trong thực thi tổng số lần N * M.
Như vậy, tổng độ phức tạp của hai vòng là O (N2).
Tương tự độ phức tạp của ba vòng là O (N3)