Was ist das große O von Linq? Wo?

Question

Ich mache einige Vergleiche darüber, wo man Elemente aus einer Liste herausfiltert. Ich bin mir nicht sicher, es direkt zu tun, was O (n) wäre oder .Where(). I made a simple example to test .Where() auf einem einfachen Datensatz. Es gibt n = 100 Elemente, und wenn ich den Debugger auf der Linie in der Funktion BigO() führe, geht es genau 100 Male, die mich denken lassen, dass .Where() auch O (n) ist. Was ich nicht herausfinden konnte war, wo die Daten während der Operation gespeichert wurden und ich war mir nicht sicher, ob das eine erhöhte Komplexität hinzufügte.

Fehle ich etwas oder ist .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() ist O (1); Es macht eigentlich keine Arbeit.

Schleifen durch die Sammlung zurückgegeben von Where() ist O (n). ..

Die O (n), die Sie sehen, ist das Ergebnis von ToList(), die ist O (n).
Wenn Sie eine Where() Abfrage an einen O (n) Algorithmus übergeben, werden Sie sehen, dass der Rückruf n mal ausgeführt wird. (unter der Annahme, dass der Algorithmus nirgends zwischengespeichert wird)

Dies wird als verzögerte Ausführung bezeichnet.

Dies trifft auf die meisten, wenn nicht alle LINQ-Anbieter zu; Es wäre für einen LINQ-Provider nicht sinnvoll, alle Aufrufe eifrig auszuführen.

---

Im Fall von LINQ zu Objekten wird davon ausgegangen, dass der Enumerator der Quellensammlung O (n) ist.
Wenn Sie eine seltsame Sammlung verwenden, die schlechter als O (n) iteriert (mit anderen Worten, wenn MoveNext() schlechter als O (1) ist), wird Where() davon begrenzt.

Um genauer zu sein, ist die zeitliche Komplexität der Aufzählung einer Where() Abfrage die gleiche wie die Zeit Komplexität der ursprünglichen Enumeration.

In ähnlicher Weise nehme ich an, dass der Rückruf O (1) ist.
Wenn dies nicht der Fall ist, müssen Sie die Komplexität des Callbacks mit der Komplexität der ursprünglichen Enumeration multiplizieren.

Answer 2

Hängt natürlich von der Quelle der Sammlung ab.

Ich stimme @SLaks nicht zu, dass der Algorithmus O(1) ist, weil eine Abfrage zu Where() weiter nach einem Kandidaten sucht, der der Bedingung entspricht. In diesem Sinne wäre es der schlimmste Fall O(n) mit n der Betrag der Arbeit, um die gesamte Sammlung vor der Where Klausel zu ergeben.

aber er hat einen Punkt auf dem Algorithmus abhängt, die die Sammlung (zum Beispiel ergibt, wenn es eine Liste, die bereits gebaut worden, um die Liste Nachgeben ist O(n) mit n der Anzahl der Elemente in der Auflistung. Das Weiteren den Algorithmus, schaut, ob es eine Übereinstimmung gibt, ist nicht notwendigerweise O(1). Wenn der Ertragsalgorithmus O(n) ist und der Übereinstimmungsalgorithmus O(m) ist, ist die Zeitkomplexität O(n*m).

Nehmen wir zum Beispiel eine Sammlung von ganzen Zahlen:

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

, wenn Sie alle Zahlen zurückkehren wollen, die mindestens zwei Mal auftreten Sie dies mit einer Where() Klausel tun könnte:

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

Die Algorithmus wäre in O(n^2)

Zweitens können Sie auch die Sammlung mit einer faulen Einstellung aufbauen:

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

Ihr Algorithmus generiert jedoch zuerst die Liste. So ist die Zeitkomplexität O(n). jedoch

Hinweis, wenn Sie die ganze Sammlung nach dem laufen, wo die timecomplexity noch O(n*m) und nichtO(n*n*m). Denn sobald ein Kandidat gefunden wurde, wird er nicht erneut geprüft.