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?Độ phức tạp của vòng lặp lồng nhau này cho vòng lặp ba là gì?
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
Ba vòng có thể có độ phức tạp lớn hơn O (n^3). – h8pathak