Krav: Du må definere en skrivebeskyttet samlingstype, som ikke vil legge til, slette eller endre samlingen, men kun spørre i samlingen. Vi håper detJo raskere forespørselen, jo bedre。
Sammenligninger av vanlige mengder
Når algoritmens kompleksitet beskrives, brukes ofte o(1), o(n), o(logn), o(logn), o(nlogn) for å uttrykke tidskompleksiteten til den tilsvarende algoritmen, som er uttrykket for algoritmens romtidskompleksitet. Den brukes ikke bare til å representere tidskompleksitet, men også til å representere romlig kompleksitet.
O etterfølges av en funksjon i parentes som indikerer forholdet mellom tid/rom brukt av en algoritme og mengden data som vokser. hvor n representerer mengden inndata.
For eksempel, hvis tidskompleksiteten er O(n), betyr det at datamengden øker flere ganger, og tidsbruken øker også flere ganger. For eksempel vanlige traverseringsalgoritmer. Et annet eksempel er tidskompleksiteten O(n^2), som betyr at når datavolumet øker n ganger, tar det tid å øke n kvadratganger, noe som er en høyere tidskompleksitet enn lineær. For eksempel er boblesortering en typisk O(n^2)-algoritme, som må skannet n × n ganger for å sortere n tall.
Et annet eksempel er O(logn), når dataene øker n ganger, tar det tid å øke logn ganger (logaritmen her er basert på 2, for eksempel, når dataene økes med 256 ganger, øker tiden som kreves bare med 8 ganger, som er lavere enn lineær. Det binære søket er algoritmen til O (logn), som eliminerer halvparten av mulighetene hver gang det finnes, og søket i 256 data trenger bare å finnes 8 ganger for å finne målet.
O(nlogn) er det samme, det vil si, n multiplisert med logn, når dataene økes med 256 ganger, øker tidsbruket med 256 * 8 = 2048 ganger. Denne kompleksiteten er høyere enn linearitet under kvadrat. Merge and sort er tidskompleksiteten til O(nlogn).
O(1) er den laveste romtidskompleksiteten, det vil si at tiden/plassen som brukes er uavhengig av størrelsen på inputdataene, uansett hvor mange ganger inputdataene økes, forblir tiden/plassen som brukes uendret. Hashing-algoritmen er en typisk O(1) tidskompleksitet, som kan finne målet etter en enkelt beregning (uavhengig av konflikter), uansett hvor store dataene er.
Denne artikkelen bruker BenchmarkDotNet-paretList、HashSet、SortedSet、DictionarySøk etter benchmarking, se følgende:
Koden er som følger:
Testresultat: Å finne en nøkkel i en ordbok eller HashSet er mye raskere enn å slå opp i en List og SortedSet. Tidskompleksiteten til Dictionary- og HashSet-algoritmene er O(1), og for å spare minne er Dictionary's Value ikke til noen nytte for oss, så jeg valgte fortsatt HashSet-lagring.
|
Publisert på 07.03.2022 16:47:50
|
|
|
|
Publisert på 07.03.2022 23:09:48
|
Vert|
Publisert på 09.03.2022 09:55:12
|
