Anforderungen: Sie müssen einen schreibgeschützten Sammlungstyp definieren, der die Sammlung nicht hinzufügt, löscht oder ändert, sondern nur die Sammlung abfragt. Wir hoffen esJe schneller die Anfrage, desto besser。
Vergleiche der gemeinsamen Mengen
Bei der Beschreibung der Komplexität des Algorithmus werden üblicherweise o(1), o(n), o(logn), o(logn), o(nlogn) verwendet, um die zeitliche Komplexität des entsprechenden Algorithmus darzustellen, was die raumzeitliche Komplexität des Algorithmus darstellt. Er wird nicht nur verwendet, um zeitliche Komplexität darzustellen, sondern auch räumliche Komplexität.
O wird von einer Funktion in Klammern gefolgt, die die Beziehung zwischen der von einem Algorithmus verbrauchten Zeit/Raum und der gewachsenen Datenmenge anzeigt. wobei n die Menge der Eingabedaten darstellt.
Wenn zum Beispiel die Zeitkomplexität O(n) beträgt, bedeutet das, dass die Datenmenge mehrfach steigt und der Zeitaufwand ebenfalls um ein Vielfaches steigt. Zum Beispiel gängige Traversal-Algorithmen. Ein weiteres Beispiel ist die Zeitkomplexität O(n^2), was bedeutet, dass bei einer Erhöhung des Datenvolumens n-fach die Zeit benötigt, um n Quadratmal zuzunehmen, was eine höhere Zeitkomplexität als lineare ist. Zum Beispiel ist das Blasensortieren ein typischer O(n^2)-Algorithmus, der n × n Mal gescannt werden muss, um n Zahlen zu sortieren.
Ein weiteres Beispiel ist O(logn), wenn die Daten n-fach zugenommen werden, dauert es Zeit, die logn-mal zu erhöhen (die logitaritmische Zahl basiert hier auf 2, zum Beispiel erhöht sich die benötigte Zeit um das 256-fache, was niedriger ist als linear). Die binäre Suche ist der Algorithmus von O (logn), der jedes Mal die Hälfte der Möglichkeiten ausschließt, wenn sie gefunden wird, und die Suche in 256 Daten muss nur 8 Mal gefunden werden, um das Ziel zu finden.
O(nlogn) ist dasselbe, das heißt, n multipliziert mit logn; wenn die Daten um das 256-fache vergrößert werden, erhöht sich der Zeitaufwand um 256 * 8 = 2048-fach. Diese Komplexität ist höher als die Linearität unterhalb des Quadrats. Merge and Sort ist die Zeitkomplexität von O(nlogn).
O(1) ist die niedrigste raumzeitliche Komplexität, das heißt, die benötigte Zeit/Raum ist unabhängig von der Größe der Eingabedaten; egal wie oft die Eingabedaten vergrößert werden, bleibt die benötigte Zeit/Fläche unverändert. Der Hashing-Algorithmus ist eine typische O(1)-Zeitkomplexität, die das Ziel nach einer einzigen Berechnung (unabhängig von Konflikten) finden kann, egal wie groß die Daten sind.
Dieser Artikel verwendet das BenchmarkDotNet-PaarList、HashSet、SortedSet、DictionaryAnfrage zum Benchmarking siehe Folgendes:
Der Code lautet wie folgt:
Testergebnis: Einen Schlüssel in einem Wörterbuch oder HashSet zu finden ist viel schneller, als in einer Liste und SortedSet nachzuschlagen. Die Zeitkomplexität der Dictionary- und HashSet-Algorithmen beträgt O(1), und um Speicher zu sparen, ist der Wert des Wörterbuchs für uns nutzlos, daher habe ich trotzdem HashSet-Speicher gewählt.
|
Veröffentlicht am 07.03.2022 16:47:50
|
|
|
|
Veröffentlicht am 07.03.2022 23:09:48
|
Vermieter|
Veröffentlicht am 09.03.2022 09:55:12
|
