Co to jest Big O of linq .where?

Question

Robię kilka porównań na temat tego, gdzie odfiltrować elementy z listy. Nie jestem pewien, aby zrobić to bezpośrednio, co byłoby O (n), lub przy użyciu .Where(). I made a simple example to test .Where() na prostym zestawie danych. Jest ich n = 100, a kiedy uruchomię debuggera na linii w funkcji BigO(), robi to dokładnie 100 razy, dzięki czemu myślę, że .Where() to także O (n). Nie mogłem się zorientować, gdzie dane były przechowywane podczas operacji i nie byłem pewien, czy to dodawanie zwiększonej złożoności.

Czy czegoś brakuje, czy jest .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() to O (1); w rzeczywistości nie wykonuje żadnej pracy.

Zapętlenie kolekcji zwrócone przez Where() to O (n). ..

O (n), który widzisz, to wynik ToList(), który to O (n).
Jeśli zdać Where() zapytanie do O (n) algorytm, będzie zobaczyć zwrotna wykonać n razy. (zakładając, że algorytm nie buforuje nigdzie)

Nazywa się to odroczoną egzekucją.

Dotyczy to większości, jeśli nie wszystkich dostawców LINQ; nie byłoby sensu, aby dostawca LINQ chętnie wykonywał wszystkie połączenia.

---

W przypadku LINQ do obiektów zakłada się, że moduł wyliczający źródła jest O (n).
Jeśli używasz jakiejś dziwnej kolekcji, która iteruje w gorszym niż O (n) (innymi słowy, jeśli jej MoveNext() jest gorsza niż O (1)), Where() będzie ograniczony przez to.

Dokładniej, złożoność czasu wyliczania zapytania Where() jest taka sama, jak złożoność czasowa pierwotnego wyliczenia.

Podobnie zakładam, że callback to O (1).
Jeśli nie, musisz pomnożyć złożoność wywołania zwrotnego przez złożoność pierwotnego wyliczenia.

Answer 2

W zależności od źródła kolekcji oczywiście.

Nie zgadzam się z @SLaks, że algorytm jest O(1), ponieważ zapytanie do Where() będzie dalej poszukiwać kandydata, który pasuje do warunku. W tym sensie najgorszy przypadek to O(n) z n ilością pracy, która da całą kolekcję przed klauzulą ​​Where.

Jednak ma punkt, który zależy od algorytmu, który generuje kolekcję (na przykład, jeśli jest to lista, która została już zbudowana, uzyskując listę to O(n) z n liczbę elementów w kolekcji.) Ponadto algorytm wygląda, jeśli jest dopasowanie, niekoniecznie musi być O(1). Jeśli algorytm wydajności to O(n) i algorytm dopasowania O(m), złożoność czasu wynosi O(n*m).

Weźmy na przykład zbiór liczb całkowitych:

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

jeśli chcesz przywrócić wszystkie liczby całkowite, które odbywają się co najmniej dwa razy można to zrobić z Where() klauzuli:

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

The Algorytm może być w O(n^2)

Po drugie można również zbudować kolekcję z leniwym ustawieniem:

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; 
    } 
} 

Twój algorytm najpierw generuje listę. Tak więc czas kompilacji jest O(n). jednak

Wskazówka jeśli iteracyjne całą kolekcję po którym timecomplexity wciąż O(n*m) i nieO(n*n*m). Dzieje się tak dlatego, że po dopasowaniu kandydata, nie zostanie on ponownie rozpatrzony.