Tìm Big-O với nhiều vòng lặp lồng nhau?

Question

int num = n/4; 
for (int i = 1; i <= num; i++) { 
    for (int j = 1; j <= n; j++) { 
     for (int k = 1; k <= n; k++) { 
      int count = 1; 
     } 
    } 
} 

Theo sách tôi đã đọc, mã này phải là O ((n^3)/4). Nhưng dường như nó không phải. để tìm Big-O cho vòng lặp lồng nhau là bạn phải nhân các giới hạn? Vì vậy, cái này phải là num * n * n hoặc n/4 * n * n.

Answer 1

O((n^3)/4) không có ý nghĩa về ký hiệu big-O vì nó có nghĩa là đo độ phức tạp như tỷ lệ của đối số. Chia cho 4 không có tác dụng vì nó thay đổi giá trị của tỷ lệ nhưng không thay đổi.

Tất cả trong số này là tương đương:

O(n^3) 
O(n^3/4) 
O(n^3*1e6) 

ngữ khác chỉ có ý nghĩa khi chúng bao gồm một thuật ngữ n, chẳng hạn như:

O(n^3/log(n)) 
O(n^3 * 10^n) 

Như Anthony Kanago đúng khi chỉ ra, đó là ước đến:

• chỉ giữ cụm từ có tỷ lệ tăng trưởng cao nhất cho số tiền: O(n^2+n) = O(n^2) .
• loại bỏ các hằng số cho sản phẩm: O(n^2/4) = O(n^2).

Ngoài ra, tôi không luôn đồng ý với quy tắc đầu tiên đó trong mọi trường hợp. Đó là một quy tắc tốt để quyết định tốc độ tăng trưởng tối đa của hàm nhưng đối với những thứ như so sánh thuật toán ^(a) nơi bạn có thể đặt giới hạn thông số đầu vào một cách thông minh, chẳng hạn như O(n^4+n^3+n^2+n) tệ hơn chỉ là O(n^4).

Trong trường hợp đó, bất kỳ điều khoản nào phụ thuộc vào thông số đầu vào sẽ được bao gồm. Trong thực tế, ngay cả các điều khoản không đổi có thể hữu ích ở đó. So sánh ví dụ O(n+1e100) với số O(n^2) - số sau sẽ vượt trội hơn trước đây trong một khoảng thời gian, cho đến khi n trở nên đủ lớn để có hiệu lực trên cụm từ constatnt.

---

^(a) Có, tất nhiên, những người có thể nói nó không nên được sử dụng theo cách như vậy nhưng thực dụng thường vượt qua chủ nghĩa giáo điều trong thế giới thực :-)

Answer 2

Từ http://en.wikipedia.org/wiki/Big_O_notation bạn có thể thấy rằng các hằng số như 1/4 không đóng vai trò xác định ký hiệu Big-O. Điều thú vị duy nhất là nó là n^3, do đó O (N^3).

Answer 3

Một kỹ thuật nhỏ. Ký hiệu Big O được dùng để mô tả sự phức tạp về 'kích thước' của đầu vào, chứ không phải giá trị số. Nếu đầu vào của bạn là một số, thì kích thước của đầu vào là số chữ số của số của bạn. Than ôi, thuật toán của bạn là O (2^N^3) với N là số chữ số.

More on this topic

Answer 4

Chính thức, mức độ phức tạp thời gian có thể suy luận như sau: