Sự phức tạp của các phương pháp từ điển này là gì?

Question

Bất cứ ai có thể giải thích sự phức tạp của các phương pháp Dictionary sau đây là gì?

ContainsKey(key) 
Add(key,value); 

Tôi đang cố gắng tìm ra sự phức tạp của một phương pháp tôi đã viết:

public void DistinctWords(String s) 
{ 
    Dictionary<string,string> d = new Dictionary<string,string>(); 
    String[] splitted = s.split(" "); 
    foreach (String ss in splitted) 
    { 
     if (!d.containskey(ss)) 
      d.add(ss,null); 
    } 
} 

Tôi giả định rằng 2 phương pháp từ điển có của log (n) sự phức tạp nơi n là số các phím trong từ điển. Điều này có đúng không?

Answer 1

Thường lệ này, tổng thể, là hiệu quả, độ phức tạp của O (m), với m là số chuỗi trong tìm kiếm của bạn.

Điều này là do Dictionary.Contains và Dictionary.Add là cả hai (thường) O (1) hoạt động.

(Hơi phức tạp hơn một chút, như Dictionary.Add có thể là O (n) cho n mục trong Từ điển, nhưng chỉ khi dung lượng từ điển nhỏ. Như vậy, nếu bạn xây dựng từ điển đủ lớn Nếu bạn chỉ sử dụng từ điển để kiểm tra sự tồn tại, bạn có thể sử dụng một số HashSet<string>.Điều này sẽ cho phép bạn viết:

public void DistinctWords(String s) 
    { 
    HashSet<string> hash = new HashSet<string>(s.Split(' ')); 

    // Use hash here... 

Như từ điển của bạn là một biến địa phương, và không được lưu trữ (ít nhất là trong mã của bạn), bạn cũng có thể sử dụng LINQ:

var distinctWords = s.Split(' ').Distinct(); 

Answer 2

Điều đó không đúng, từ điển chung/tra cứu có thể bắt đầu bằng O (1). Để làm điều này, nó sẽ tạo ra một băm từ khóa bạn đang tìm kiếm và chỉ so sánh nó với các mục có cùng một băm - với một thuật toán băm tốt được coi là O (1) tổng thể (amortized O (1) - chỉ trong nhân dịp hiếm hoi mà công suất phải được tăng thêm cho bạn có O (n)).

Answer 3

Cả hai phương pháp có liên tục phức tạp:

• containsKey (key) - O (1)
• Add (key, value) - O (1)

Answer 4

Nó được viết trong tài liệu cho Dictionary ...

Lớp chung chung của từ điển cung cấp ánh xạ từ tập hợp khóa cho một tập hợp các giá trị. Mỗi bổ sung vào từ điển bao gồm một giá trị và khóa liên quan của nó. Việc lấy một giá trị bằng cách sử dụng khóa của nó là rất nhanh, gần với O (1), bởi vì lớp Từ điển được thực hiện như một bảng băm.

Và đối với Add chức năng:

Nếu Count là ít hơn khả năng, phương pháp này phương pháp tiếp cận một O (1) hoạt động. Nếu công suất phải được tăng lên để thích ứng với phần tử mới, phương thức này trở thành một hoạt động O (n), trong đó n là Đếm.

Answer 5

Cả hai đều là hằng số thời gian :

http://msdn.microsoft.com/en-us/library/kw5aaea4.aspx

http://msdn.microsoft.com/en-us/library/k7z0zy8k.aspx

Một báo trước tuy nhiên:

"Nếu Đếm nhỏ hơn dung lượng, phương pháp này tiếp cận hoạt động O (1). Nếu khả năng đó phải được tăng để phù hợp với các yếu tố mới, phương pháp này sẽ trở thành một hoạt động O (n), trong đó n là Count."

Answer 6

Các containsKey và bổ sung phương thức gần gũi với O (1).

containsKey tài liệu hướng dẫn:.

phương pháp này tiếp cận một O (1) hoạt động

Thêm tài liệu:

Nếu Đếm nhỏ hơn dung lượng, phương pháp này tiếp cận hoạt động O (1) . Nếu công suất phải được tăng lên để chứa phần tử mới, phương pháp này trở thành một hoạt động O (n), trong đó n là Đếm.

Nếu bạn đang sử dụng Framework 3.5 hoặc mới hơn, bạn có thể sử dụng một HashSet<T> thay vì một từ điển với các giá trị giả:

public void DistinctWords(String s) { 
    HashSet<string> d = new HashSet<string(s.split(" ")); 
}