Độ phức tạp về thời gian được đặt trong Java

Question

Ai đó có thể cho tôi biết độ phức tạp của mã dưới đây không?

a là một mảng int.

Set<Integer> set = new HashSet<Integer>(); 
for (int i = 0; i < a.length; i++) { 
    if (set.contains(arr[i])) { 
     System.out.println("Hello"); 
    } 
    set.add(arr[i]); 
} 

Tôi nghĩ rằng đó là O (n), nhưng tôi không chắc chắn vì nó được sử dụng Set và điều này có chứa các phương pháp là tốt. Nó cũng đang gọi phương thức add của set.

Có ai có thể xác nhận và giải thích độ phức tạp của toàn bộ mã trên không? Ngoài ra, nó sẽ mất bao nhiêu không gian?

Answer 1

tôi tin O của nó (n) bởi vì bạn lặp qua mảng, và contains và add nên thời gian liên tục bởi vì nó là một băm dựa bộ. Nếu nó không được dựa trên băm và lặp lại yêu cầu trên toàn bộ thiết lập để thực hiện tra cứu, giới hạn trên sẽ là n^2.

Số nguyên là không thay đổi, do đó độ phức tạp của không gian sẽ là 2n, mà tôi tin đơn giản hóa chỉ là n, vì các hằng số không quan trọng.

Nếu bạn có đối tượng trong mảng và thiết lập, thì bạn sẽ có tham chiếu 2n và n đối tượng, vì vậy bạn đang ở 3n, vẫn là giới hạn về không gian tuyến tính (lần một hằng số).

EDIT-- yep "Lớp này cung cấp hiệu suất thời gian không đổi cho các hoạt động cơ bản (thêm, xóa, chứa và kích thước), giả sử hàm băm phân tán các phần tử chính xác giữa các nhóm."

xem here.