Zeit/Raum-Komplexität für .net intersect() -Methode

Question

Diese vorherige SO Beitrag beschreibt die .NET Intersect() -Methode:

Intersection of two sets in most optimized way

Es beschreibt die großen o Komplexität des Verfahrens, wie o (m + n). Ist das die große Kompliziertheit für beide Zeit und Platz?

Außerdem las ich irgendwo anders, dass n vor m in großer o Notation gehen sollte, so dass die obige Komplexität als o (n + m) geschrieben werden sollte. Ist n vor m die richtige Reihenfolge oder ist die Reihenfolge dieser Variablen nicht wichtig (sehr) mit großer o-Notation?

Answer 1

(1) Die Antwort beschreibt das Erstellen eines Hashsets aus einer Liste und das Überprüfen der Elemente in der anderen Liste dagegen. Die Komplexität des Platzes ergibt sich aus dem Aufbau des Hashsets. Die Größe des hashsets ist proportional zur Anzahl der Elemente, die in ihm platziert werden, entweder m oder n, abhängig davon, aus welcher Sammlung Sie das Hashset erstellen. Nehmen wir an, Sie bauen im schlimmsten Fall das Hash-Set aus dem größeren Set auf. Dann ist die Raumkomplexität O (max (m, n)). Diese Komplexitätsklasse ist identisch mit O (m + n). Warum? Weil max (m, n) < 1 * (m + n) für alle positiven m, n; und m + n < = 2 * max (m, n) für alle positiven m, n. Ja, die Komplexität von Zeit und Raum des beschriebenen Verfahrens ist sowohl O (m + n) als auch äquivalent O (max (m, n)).

(2) m + n < = 1 * (n + m) für alle positiven m, n; und n + m < = 1 * (m + n) für alle positiven m, n. Daher ist O (m + n) identisch mit O (n + m).

Answer 2

Ist das die große Komplexität für Zeit und Raum?

Wenn Sie mit O (m + n) -Methode werden, wird der Raum Komplexität sein O (m < n ? m : n). Warum? Sie können das kleinere dieser m- und n-Größen im Speicher behalten und dann 1 Element auf einmal von dem größeren lesen, um zu testen, ob das eine Element des größeren in dem kleineren Element ist. Andernfalls, wenn Sie beide aus dem Speicher behalten, wird die Komplexität des Speicherplatzes O (1) werden, während die Komplexität der Zeit auf O (mn) schießen wird.

Ist n vor der richtigen Reihenfolge oder spielt die Reihenfolge dieser Variablen keine Rolle (sehr) mit großer o-Notation?

Da m + n = n + m, spielt es keine Rolle. Wenn die Komplexität etwas wie O (m Log n) oder O (mn) wäre, dann bin ich sicher, dass Sie es nicht als O (n Log m) oder O (nm) schreiben können.