Tricky Big-O complexity

Question

public void foo(int n, int m) { 
    int i = m; 

    while (i > 100) { 
     i = i/3; 
    } 
    for (int k = i ; k >= 0; k--) { 
     for (int j = 1; j < n; j *= 2) { 
      System.out.print(k + "\t" + j); 
     } 
     System.out.println(); 
    } 
} 

Tôi nhận thấy độ phức tạp sẽ là O (logn).
Đó là một sản phẩm của vòng lặp bên trong, vòng lặp bên ngoài - sẽ không bao giờ được thực thi hơn 100 lần, vì vậy nó có thể được bỏ qua.

Điều tôi không chắc chắn là mệnh đề thời gian, liệu nó có nên được kết hợp vào độ phức tạp của Big-O không? Đối với các giá trị i rất lớn, nó có thể tác động hoặc hoạt động số học, không quan trọng trên thang đo nào, được tính là hoạt động cơ bản và có thể bỏ qua?

Answer 1

Vòng while là O(log m) vì bạn tiếp tục chia m cho đến khi nó ở dưới hoặc bằng 100.

Vì 100 là hằng số trong trường hợp của bạn nên có thể bỏ qua.

Vòng lặp bên trong là O(log n) như bạn đã nói, vì bạn nhân j cho 2 cho đến khi vượt quá n.

Do đó tổng độ phức tạp là O(log n + log m).

hoặc phép tính số học, không quan trọng về quy mô nào, được tính là hoạt động cơ bản và có thể bỏ qua?

Thao tác số học thường có thể bị bỏ qua, có. Tuy nhiên, nó cũng phụ thuộc vào ngôn ngữ. Điều này trông giống như Java và có vẻ như bạn đang sử dụng các kiểu nguyên thủy. Trong trường hợp này, bạn có thể xem xét các phép toán số học O(1), vâng. Nhưng nếu bạn sử dụng các số nguyên lớn chẳng hạn, điều đó không thực sự ok nữa, vì phép cộng và phép nhân không còn là O(1).

Answer 2

Độ phức tạp là O (log m + log n).

Vòng lặp while thực thi log3 (m) lần - hằng số (log3 (100)). Vòng lặp for bên ngoài thực hiện một số lần không đổi (khoảng 100) và vòng lặp bên trong thực thi log2 (n) lần.

Answer 3

Vòng lặp while chia giá trị của m bởi một yếu tố của 3, do đó số lượng các hoạt động đó sẽ được đăng nhập (cơ sở 3) m

Đối với cho vòng bạn có thể nghĩ đến số lượng các hoạt động như 2 summations -

tổng kết (k = 0 đến i) [tổng kết (j = 0 đến lg n) (1)] tổng kết (k = 0 đến i) [lg n + 1] (lg n + 1) (i + 1) sẽ là tổng số hoạt động, trong đó thuật ngữ log chiếm ưu thế.

Đó là lý do mức độ phức tạp là O (log (base3) m + n lg) Ở đây lg dùng để đăng nhập vào căn 2