Krav: Du skal definere en skrivebeskyttet samlingstype, som ikke tilføjer, sletter eller ændrer samlingen, men kun forespørger samlingen. Det håber viJo hurtigere forespørgselen er, jo bedre。
Sammenligninger af almindelige mængder
Når algoritmens kompleksitet beskrives, bruges o(1), o(n), o(logn), o(logn), o(nlogn) ofte til at udtrykke tidskompleksiteten for den tilsvarende algoritme, som er udtrykket for algoritmens rum-tidsmæssige kompleksitet. Det bruges ikke kun til at repræsentere tidsmæssig kompleksitet, men også til at repræsentere rumlig kompleksitet.
O efterfølges af en funktion i parentes, der angiver forholdet mellem den tid/plads, en algoritme bruger, og mængden af voksede data. hvor n repræsenterer mængden af inputdata.
For eksempel, hvis tidskompleksiteten er O(n), betyder det, at mængden af data øges flere gange, og tidsforbruget også stiger flere gange. For eksempel almindelige traverseringsalgoritmer. Et andet eksempel er tidskompleksiteten O(n^2), hvilket betyder, at når datamængden øges n gange, tager det tid at øge n kvadratgange, hvilket er en højere tidskompleksitet end lineær. For eksempel er boblesortering en typisk O(n^2)-algoritme, som skal scannes n × n gange for at sortere n tal.
Et andet eksempel er O(logn), når dataene øges n gange, tager det tid at øge logn gange (logaritmen her er baseret på 2, for eksempel, når dataene øges med 256 gange, øges den nødvendige tid kun med 8 gange, hvilket er lavere end lineært. Den binære søgning er algoritmen O (logn), som eliminerer halvdelen af mulighederne hver gang den findes, og søgningen i 256 data behøver kun at blive fundet 8 gange for at finde målet.
O(nlogn) er det samme, det vil sige, n ganget med logn, når dataene øges med 256 gange, øges tidsforbruget med 256 * 8 = 2048 gange. Denne kompleksitet er højere end lineariteten under kvadrat. Merge and sort er tidskompleksiteten i O(nlogn).
O(1) er den laveste rum-tidslige kompleksitet, det vil sige, at den tid/plads, der forbruges, er uafhængig af størrelsen af inputdataene; uanset hvor mange gange inputdataene øges, forbliver den forbrugte tid/plads uændret. Hashing-algoritmen er en typisk O(1) tidskompleksitet, som kan finde målet efter en enkelt beregning (uanset konflikter), uanset hvor store dataene er.
Denne artikel bruger BenchmarkDotNet-parretList、HashSet、SortedSet、DictionaryForespørgsel om benchmarking, se følgende:
Koden er som følger:
Testresultat: At finde en nøgle i en ordbog eller hashSet er meget hurtigere end at slå op i en List og SortedSet. Tidskompleksiteten for ordbogs- og hashsetalgoritmerne er O(1), og for at spare hukommelse er ordbogens værdi ikke til nogen nytte for os, så jeg valgte stadig HashSet-lagring.
|
Opslået på 07/03/2022 16.47.50
|
|
|
|
Opslået på 07/03/2022 23.09.48
|
Udlejer|
Opslået på 09/03/2022 09.55.12
|
