Tôi chỉ đọc another question và mã này hấp dẫn tôi:Tại sao mã này được coi là O (N^6) trong ký hiệu Big Oh?
for(i = 0; i < n; i++)
{
for(j = 0; j < i*i; j++)
{
for(k = 0; k < i*j; k++)
{
pseudo_inner_count++;
for(l = 0; l < 10; l++);
}
}
}
Tôi không hiểu làm thế nào điều này có thể O (N^6). Ai đó có thể phá vỡ nó cho tôi?
Trên thực tế nó là:
Các vòng lặp được lồng nhau vì vậy chúng tôi phải nhân chúng lại với nhau (bạn có hiểu tại sao không?). Tổng là O (N) * O (N^2) * O (N^3) = O (N^6).
tôi sẽ nói:
Bất kỳ ai đã bỏ phiếu, hãy giải thích lý do. – karlphillip
Tôi đã không downvote, nhưng tôi không thấy làm thế nào các vòng trong cùng có thể được O (n) khi nó thực hiện trong thời gian không đổi, bất kể giá trị của n. – antinome
Vâng, điều này có vẻ như O (N^5) với tôi – bdares
Đó là
n cho là người đầu tiên vòng n ² cho phần thứ hai vòng lặp n³ cho vòng lặp thứ ba
Các vòng lặp bên trong là O (1)
Tổng là O (n⁶).
Lý do vòng thứ ba là n³ là vì khi bạn nghĩ về nó j đạt n² và tôi đạt đến n, vì vậy i * j đạt đến n³.
Ok, vì vậy kết quả cuối cùng đạt được thông qua phép nhân các đánh giá của mỗi vòng lặp, và không thông qua một tổng (như @Pascal gợi ý). Người khác có thể xác nhận điều này không? – karlphillip
Pascal đã không thực sự làm tổng. Anh nhân với n * n^2 * n^2 * n và nhận n^6. Nó có thể trông giống như một tổng bởi vì các số mũ cộng với nhau nhưng đó chỉ là cách số mũ làm việc trong toán học. –
Những upvotes được xác nhận = D –