Big O của linq. Ở đâu?

Question

Tôi đang thực hiện một số so sánh về vị trí lọc các mục khỏi danh sách. Tôi không chắc chắn làm điều đó trực tiếp mà sẽ là O (n), hoặc sử dụng .Where(). I made a simple example to test .Where() trên một tập dữ liệu đơn giản. Có n = 100 mục, và khi tôi chạy trình gỡ rối trên dòng trong hàm BigO() nó đi chính xác 100 lần khiến tôi nghĩ rằng .Where() cũng là O (n). Những gì tôi không thể tìm ra là nơi dữ liệu được lưu trữ trong quá trình hoạt động và tôi không chắc liệu điều đó có làm tăng thêm sự phức tạp nào không.

Tôi có thiếu gì đó hay không .Where() O (n)?

public class ListerFactory 
{ 

public class Lister 
{ 
    bool includeItem { get; set; } 
} 

List<Lister> someList { get; set; } 

public ListerFactory() 
{ 
    someList = new List<Lister>(); 
    BuildLister(); 
}  

public void BuildLister() 
{ 
    for(int i = 0; i < 100; i++) 
    { 
    var inc = new Lister(); 
    inc.includeItem = i % 2; 
    someList.Add(inc); 
    } 
    BigO(); 
} 

public void BigO() 
{ 
    someList = someList.Where(thisList => thisList.includeItem == true).ToList(); 
} 
} 

Answer 1

Where() là O (1); nó không thực sự làm bất kỳ công việc nào.

Lặp qua bộ sưu tập được trả lại bởi Where() là O (n). ..

O (n) mà bạn đang xem là kết quả của ToList(), trong đó là O (n).
Nếu bạn chuyển một truy vấn Where() đến một thuật toán O (n), bạn sẽ thấy lệnh gọi lại thực thi n lần. (giả sử thuật toán không lưu trữ ở bất cứ đâu)

Đây được gọi là thực thi hoãn lại.

Điều này đúng về hầu hết nếu không phải tất cả các nhà cung cấp LINQ; nó sẽ không có ý nghĩa đối với một nhà cung cấp LINQ để háo hức thực hiện tất cả các cuộc gọi.

---

Trong trường hợp LINQ đối tượng, điều này giả định rằng điều tra thu thập nguồn là O (n).
Nếu bạn đang sử dụng một số bộ sưu tập lạ lặp lại tệ hơn O (n) (nói cách khác, nếu số MoveNext() của nó thấp hơn O (1)), Where() sẽ bị ràng buộc bởi điều đó.

Để chính xác hơn, độ phức tạp về thời gian liệt kê truy vấn Where() giống với độ phức tạp thời gian của điều tra ban đầu.

Tương tự, tôi giả định rằng cuộc gọi lại là O (1).
Nếu không, bạn cần phải nhân sự phức tạp của cuộc gọi lại với độ phức tạp của điều tra ban đầu.

Answer 2

Tùy thuộc vào nguồn của tập hợp khóa học.

Tôi không đồng ý với @SLaks rằng thuật toán là O(1) vì truy vấn Where() sẽ tiếp tục tìm kiếm một ứng cử viên phù hợp với điều kiện. Trong trường hợp đó, trường hợp xấu nhất là O(n) với số n số lượng công việc để mang lại toàn bộ bộ sưu tập trước mệnh đề Where.

Tuy nhiên, ông có điểm phụ thuộc vào thuật toán thu thập bộ sưu tập (ví dụ: nếu danh sách đã được xây dựng để tạo danh sách là O(n) với số lượng mặt hàng trong bộ sưu tập đó là n. nếu có một kết quả phù hợp không nhất thiết phải là O(1). Nếu thuật toán lợi nhuận là O(n) và thuật toán đối sánh O(m) độ phức tạp thời gian là O(n*m).

Đưa ví dụ một tập hợp các số nguyên:

int[] test = new int[] {1,2,3,4,5,6,7,8,9,10,7,5,0,1,5,6}; 

nếu bạn muốn quay trở lại tất cả các số nguyên người xảy ra ít nhất hai lần bạn có thể làm điều này với một điều khoản Where():

test.Where(x => test.Count(y => x == y) >= 2); 

Các thuật toán sẽ ở trong O(n^2)

Thứ hai, bạn cũng có thể tạo bộ sưu tập với cài đặt lười:

public IEnumerable<int> GenerateCollection() { 
    //some very complex calculation, here replaced by a simple for loop 
    for(int i = 0; i < 150; i++) { 
     yield return i; 
    } 
} 

Thuật toán của bạn trước tiên sẽ tạo danh sách. Vì vậy, độ phức tạp là O(n).

Tuy nhiên, thông báo nếu bạn lặp lại toàn bộ bộ sưu tập sau khi độ phức tạp vẫn là O(n*m) và khôngO(n*n*m). Đó là bởi vì khi một ứng cử viên đã được kết hợp, nó sẽ không được xem xét lại.