Vaatimukset: Sinun täytyy määritellä vain luku -tyyppinen kokoelmatyyppi, joka ei lisää, poista tai muokkaa kokoelmaa, vaan ainoastaan kyselyy kokoelmasta. ToivommeMitä nopeampi kysely, sitä parempi。
Yleiset joukkojen vertailut
Algoritmin monimutkaisuutta kuvattaessa käytetään yleisesti o(1), o(n), o(logn), o(logn), o(logn) ilmaisemaan vastaavan algoritmin aikakompleksisuutta, joka on algoritmin spatio-ajallisen monimutkaisuuden ilmaiseminen. Sitä käytetään paitsi ajallisen monimutkaisuuden myös spatiaalisen monimutkaisuuden kuvaamiseen.
O:ta seuraa suluissa oleva funktio, joka ilmaisee algoritmin kuluttaman ajan/tilan ja kasvatetun datamäärän välisen yhteyden. missä n edustaa syötedatan määrää.
Esimerkiksi, jos aikakompleksisuus on O(n), se tarkoittaa, että datan määrä kasvaa useita kertoja ja ajankulutus moninkertaiseksi. Esimerkiksi yleiset kulkualgoritmit. Toinen esimerkki on aikakompleksisuus O(n^2), joka tarkoittaa, että kun datan tilavuus kasvaa n-kertaiseksi, sen kasvaminen kestää ajan n neliökertaa, mikä on aikakompleksisuus suurempi kuin lineaarinen. Esimerkiksi kuplalajittelu on tyypillinen O(n^2)-algoritmi, joka täytyy skannata n × n kertoa n numeron lajittelemiseksi.
Toinen esimerkki on O(logn), jossa kun data kasvaa n-kertaiseksi, logn-aikojen kasvattaminen vie aikaa (logari perustuu tässä 2:een, esimerkiksi kun data kasvaa 256-kertaiseksi, tarvittava aika kasvaa vain 8-kertaiseksi, mikä on vähemmän kuin lineaarinen). Binäärihaku on algoritmi O (logn), joka poistaa puolet mahdollisuuksista joka kerta, kun se löydetään, ja haku 256 datasta riittää löytämään vain 8 kertaa löytääkseen kohteen.
O(nlogn) on sama, eli n kerrottuna logn:lla, kun dataa kasvatetaan 256-kertaiseksi, ajankulutus kasvaa 256 * 8 = 2048 kertaa. Tämä monimutkaisuus on suurempi kuin lineaarisuus neliön alapuolella. Merge and sort on O(nlogn):n aikakompleksisuus.
O(1) on alin spatiotempraalinen monimutkaisuus, eli kulutettu aika/tila on riippumaton syötedatan koosta, riippumatta siitä, kuinka monta kertaa syötedataa kasvatettaisiin, kulutettu aika/tila pysyy muuttumattomana. Hajautusalgoritmi on tyypillinen O(1)-aikakompleksisuus, joka voi löytää kohteen yhden laskennan jälkeen (ristiriidoista riippumatta), riippumatta datan koosta.
Tässä artikkelissa käytetään BenchmarkDotNet-pariaList、HashSet、SortedSet、DictionaryVertailukysely seuraavista asioista:
Koodi on seuraava:
Testitulos: Avaimen löytäminen sanakirjasta tai hashSetistä on paljon nopeampaa kuin etsiminen listasta ja SortedSetistä. Sanakirja- ja HashSet-algoritmien aikavaativuus on O(1), ja muistin säästämiseksi Sanakirjan arvosta ei ole meille hyötyä, joten valitsin silti HashSet-tallennuksen.
|
Julkaistu 7.3.2022 16.47.50
|
|
|
|
Julkaistu 7.3.2022 23.09.48
|
Vuokraisäntä|
Julkaistu 9.3.2022 9.55.12
|
