phức tạp về thời gian để lặp qua danh sách mảng

Question

Tôi có danh sách mảng mà tôi lặp qua. Trong mỗi lần lặp tôi gọi get() để có được một yếu tố, và nếu mục mà đi một số điều kiện, nó được thêm vào danh sách mảng mới sử dụng add()

List<Item> items = new ArrayList<Item>(); 
List<Item> lessItems = new ArrayList<Item>(); 
for(int index = 0; index < items.size(); index++){ 
    Item toCheck = items.get(i); 
    if(toCheck meets some condition){ 
     lessItems.add(toCheck); 
    } 
} 

Tôi không chắc chắn những gì mức độ phức tạp thời gian là ở đây. Tôi đang gọi get() trên tất cả các mục để đó là O (n). Sau đó, tôi cũng gọi add() trên tất cả các mục có khả năng để có một O (n) khác. Không quá chắc chắn về điều này.

Answer 1

Big-O và các ký hiệu tương tự là giới hạn tiệm cận về thời gian phức tạp. Chúng loại bỏ hệ số số và được sử dụng để ước tính thời gian chạy như một hàm có kích thước đầu vào.

Vì vậy, 2*n, 3*n, v.v. được thể hiện dưới dạng O(n) và 2*nlog(n), 3*nlog(n), v.v. được thể hiện là O(nlog(n)).

Vì thao tác thêm() chỉ chèn một phần tử trong trường hợp này, thời gian chạy của nó xấp xỉ, (some small constant)k*1, cho tổng thời gian chạy là (some constant)j*(n+some constant(k)), nói cách khác là j*n hoặc O(n).

Trong trường hợp này và tất cả các trường hợp tương tự như vậy, bất cứ liên tục k nhân n sẽ được biểu diễn như O(n) có nghĩa là thời gian chạy thay đổi tuyến tính với kích thước của ArrayList đầu vào.

Answer 2

Tất cả các câu trả lời khác là sai tại đây.

1. vòng đầu tiên của bạn cho lặp lại danh sách items: độ phức tạp là O(n)
2. Insert mỗi mục để kết thúc danh sách lessItems: trong mảng bình thường nó sẽ được O(n) như những người khác nói. Nhưng Java thực hiện cho ArrayList sử dụng amortized array. Điều này có nghĩa là khi chèn vào cuối mảng, thuật toán chỉ có giá là Amortized O(1). Hoặc bạn có thể nói O(1)

Vì vậy, sự phức tạp của mã của bạn là: O(n) * amortized O(1). Nói tóm lại là O(n)

Một tài liệu tham khảo:

dynamic array

lưu ý bổ sung 1:

Nếu phức tạp của chèn vào cuối mảng là O(N), vì vậy tổng độ phức tạp là O(N^2), không O (2 * N) như các câu trả lời khác cho biết. Bởi vì tổng phức tạp cho chèn sẽ là: 1 + 2 + 3 + ...+ n = n*(n+1)/2

addtional Note 2:

như official document trạng thái:

Kích thước, isEmpty, nhận được, thiết lập, hoạt động iterator, và listIterator chạy trong thời gian không đổi.Hoạt động bổ sung chạy trong thời gian không đổi được phân bổ, nghĩa là, thêm phần tử n yêu cầu thời gian O (n). Tất cả các hoạt động khác chạy trong thời gian tuyến tính (nói gần). Hệ số không đổi thấp so với việc thực hiện LinkedList.

Lưu ý bổ sung 3:

Đây là logic của grow phương pháp mà tôi đã lấy từ mã nguồn java chính thức:

private void ensureExplicitCapacity(int minCapacity) { 
     modCount++; 

     // overflow-conscious code 
     if (minCapacity - elementData.length > 0) 
      grow(minCapacity); 
    } 

private void grow(int minCapacity) { 
     // overflow-conscious code 
     int oldCapacity = elementData.length; 
     int newCapacity = oldCapacity + (oldCapacity >> 1); 
     if (newCapacity - minCapacity < 0) 
      newCapacity = minCapacity; 
     if (newCapacity - MAX_ARRAY_SIZE > 0) 
      newCapacity = hugeCapacity(minCapacity); 
     // minCapacity is usually close to size, so this is a win: 
     elementData = Arrays.copyOf(elementData, newCapacity); 
    } 

Khi mã nguồn đã nói, khi chương trình thêm phần tử tạo kích thước mảng lớn hơn dung lượng hiện tại, mảng sẽ được tăng lên. kích thước mới của mảng trưởng thành sẽ là:

int newCapacity = oldCapacity + (oldCapacity >> 1); 

Đây là một thủ thuật mà làm cho chèn là amortized O(1)

Answer 3

Bạn đang làm một lần lặp, và đó là O (n).

Bạn cũng đang thêm các mục vào một ArrayList, đó là O (1) (Amortized)

Bắt một chỉ số cũng là O (1).

Vì vậy, bạn thực hiện O (n) lần, hoạt động của O (1), sẽ là O (n).