Krav: Du behöver definiera en skrivskyddad samlingstyp, som inte lägger till eller tar bort samlingen, utan endast frågar samlingen. Vi hoppasJu snabbare frågan är, desto bättre。
Jämförelser av gemensamma mängder
När algoritmens komplexitet beskrivs används ofta o(1), o(n), o(logn), o(logn), o(nlogn) för att uttrycka tidskomplexiteten för den motsvarande algoritmen, vilket är uttrycket för algoritmens rumsliga komplexitet. Den används inte bara för att representera tidsmässig komplexitet, utan även för att representera rumslig komplexitet.
O följs av en funktion inom parentes som anger sambandet mellan den tid/plats som en algoritm förbrukar och mängden data som växer. där n representerar mängden indata.
Till exempel, om tidskomplexiteten är O(n), betyder det att mängden data ökar flera gånger och tidsförbrukningen ökar flera gånger. Till exempel vanliga traverseringsalgoritmer. Ett annat exempel är tidskomplexiteten O(n^2), vilket innebär att när datavolymen ökar n gånger tar det tid att öka n kvadratgånger, vilket är en högre tidskomplexitet än linjär. Till exempel är bubbelsortering en typisk O(n^2)-algoritm, som behöver skannas n × n gånger för att sortera n tal.
Ett annat exempel är O(logn), när datan ökar n gånger tar det tid att öka logn gånger (logaritmen här baseras på 2, till exempel, när datan ökas 256 gånger ökar den tid som krävs bara 8 gånger, vilket är lägre än linjärt. Den binära sökningen är algoritmen för O (logn), som eliminerar hälften av möjligheterna varje gång den hittas, och sökningen i 256 data behöver bara hittas 8 gånger för att hitta målet.
O(nlogn) är samma, det vill säga, n multiplicerat med logn, när datan ökar med 256 gånger ökar tidsförbrukningen med 256 * 8 = 2048 gånger. Denna komplexitet är högre än linjäriteten under kvadrat. Merge and sort är tidskomplexiteten i O(nlogn).
O(1) är den lägsta spatiotemporala komplexiteten, det vill säga att den tid/utrymme som förbrukas är oberoende av storleken på indatan, oavsett hur många gånger indatan ökas förblir den förbrukade tiden/utrymmet oförändrat. Hashningsalgoritmen har en typisk O(1) tidskomplexitet, som kan hitta målet efter en enda beräkning (oavsett konflikter), oavsett hur stor datan är.
Denna artikel använder BenchmarkDotNet-paretList、HashSet、SortedSet、DictionarySök efter benchmarking, se följande:
Koden är följande:
Testresultat: Att hitta en nyckel i en ordbok eller hashset går mycket snabbare än att slå upp i en List och SortedSet. Tidskomplexiteten för Dictionary- och HashSet-algoritmerna är O(1), och för att spara minne är Dictionary's Value värdefullt för oss oanvändbart, så jag valde ändå HashSet-lagring.
|
Publicerad på 2022-03-07 16:47:50
|
|
|
|
Publicerad på 2022-03-07 23:09:48
|
Hyresvärd|
Publicerad på 2022-03-09 09:55:12
|
