Ký hiệu Java Big O của 3 vòng lặp lồng nhau của nhật ký (n)

Question

Ký hiệu Big O sẽ là gì cho các vòng lồng nhau sau đây?

 for (int i = n; i > 0; i = i/2){ 
     for (int j = n; j > 0; j = j/2){ 
      for (int k = n; k > 0; k = k/2){ 
       count++; 
      } 
     } 
    } 

những suy nghĩ của tôi là: mỗi vòng lặp là O(log2(n)) như vậy là nó đơn giản như nhân

O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3) 

Answer 1

Vâng, đó là chính xác.

Một cách để tìm ra độ phức tạp lớn-O của các vòng lồng nhau mà giới hạn của chúng không phụ thuộc vào nhau là làm việc từ trong ra ngoài. Vòng lặp bên trong nhất làm O (log n) làm việc. Vòng lặp thứ hai chạy O (log n) lần và O (log n) làm việc mỗi lần, do đó, nó hoạt động O (log n). Cuối cùng, vòng ngoài cùng chạy O (log n) lần và thực hiện O (log n) hoạt động trên mỗi lần lặp, do đó tổng công việc được thực hiện là O (log n).

Hy vọng điều này sẽ hữu ích!

Answer 2

Có bạn đã đúng.

Cách dễ dàng để tính toán -

for(int i=0; i<n;i++){ // n times 
    for(int j=0; j<n;j++){ // n times 
    } 
} 

Ví dụ này của vòng lặp lồng nhau đơn giản. Ở đây Big-O của mỗi vòng lặp O (n) và nó được lồng vào nhau thường là O (n * n) là O (n^2) thực tế Big-O. Và trong trường hợp của bạn -

for (int i = n; i > 0; i = i/2){ // log(n) 
    for (int j = n; j > 0; j = j/2){ // log(n) 
     for (int k = n; k > 0; k = k/2){ // log(n) 
      count++; 
     } 
    } 
} 

Đó là trong vòng lặp lồng nhau trong đó mỗi vòng lặp Big-O là O(log(n)) vì vậy tất cả sự phức tạp lại với nhau sẽ O(log(n)^3)

Answer 3

Thật vậy, giả định của bạn là đúng. Bạn có thể hiển thị nó có phương pháp như sau: