Vereisten: Je moet een alleen-lezen collectietype definiëren, dat de collectie niet toevoegt, verwijdert of apast, maar alleen de collectie opvraagt. Dat hopen weHoe sneller de query, hoe beter。
Vergelijkingen van gemeenschappelijke verzamelingen
Bij het beschrijven van de complexiteit van het algoritme worden o(1), o(n), o(logn), o(logn), o(nlogn) vaak gebruikt om de tijdscomplexiteit van het bijbehorende algoritme uit te drukken, wat de uitdrukking is van de ruimtelijke en temporele complexiteit van het algoritme. Het wordt niet alleen gebruikt om temporele complexiteit weer te geven, maar ook om ruimtelijke complexiteit weer te geven.
O wordt gevolgd door een functie tussen haakjes die de relatie aangeeft tussen de tijd/ruimte die door een algoritme wordt verbruikt en de hoeveelheid gegroeide data. waarbij n de hoeveelheid invoergegevens vertegenwoordigt.
Als de tijdscomplexiteit bijvoorbeeld O(n) is, betekent dit dat de hoeveelheid data meerdere keren toeneemt en de tijdsopname ook meerdere keren toeneemt. Bijvoorbeeld veelvoorkomende traversal-algoritmen. Een ander voorbeeld is de tijdscomplexiteit O(n^2), wat betekent dat wanneer het datavolume n keer toeneemt, het tijd kost om n kwadraaten keren toe te nemen, wat een hogere tijdscomplexiteit is dan lineair. Bijvoorbeeld, bubbelsortering is een typisch O(n^2)-algoritme, dat n × n keer gescand moet worden om n getallen te sorteren.
Een ander voorbeeld is O(logn), wanneer de data n keer toeneemt, duurt het tijd om de logn keer te verhogen (de logaritme hier is gebaseerd op 2, bijvoorbeeld, wanneer de data met 256 keer wordt vergroot, neemt de benodigde tijd slechts 8 keer toe, wat lager is dan lineair. De binaire zoekopdracht is het algoritme van O (logn), dat elke keer dat het wordt gevonden de helft van de mogelijkheden uitsluit, en de zoekopdracht in 256 gegevens hoeft slechts 8 keer gevonden te worden om het doel te vinden.
O(nlogn) is hetzelfde, dat wil zeggen, n vermenigvuldigd met logn; wanneer de data met 256 keer wordt vergroot, neemt het tijdsverbruik toe met 256 * 8 = 2048 keer. Deze complexiteit is hoger dan lineariteit onder het kwadraat. Samenvoegen en sorteren is de tijdscomplexiteit van O(nlogn).
O(1) is de laagste ruimtelijke complexiteit, dat wil zeggen, de tijd/ruimte die wordt verbruikt is onafhankelijk van de grootte van de invoerdata; ongeacht hoe vaak de invoerdata wordt vergroot, blijft de tijd/ruimte ongewijzigd. Het hashing-algoritme is een typische O(1) tijdcomplexiteit, die het doel kan vinden na één enkele berekening (ongeacht conflicten), ongeacht hoe groot de data is.
Dit artikel gebruikt het BenchmarkDotNet-paarList、HashSet、SortedSet、DictionaryZoek naar benchmarking, zie het volgende:
De code is als volgt:
Testresultaat: Een sleutel vinden in een woordenboek of hashset is veel sneller dan opzoeken in een List en SortedSet. De tijdscomplexiteit van de Dictionary- en HashSet-algoritmen is O(1), en om geheugen te besparen is de Dictionary's Value voor ons nutteloos, dus heb ik toch voor HashSet-opslag gekozen.
|
Geplaatst op 07-03-2022 16:47:50
|
|
|
|
Geplaatst op 07-03-2022 23:09:48
|
Huisbaas|
Geplaatst op 09-03-2022 09:55:12
|
