Zahteve: Morate definirati vrsto zbirke, ki je samo za branje, ki ne bo dodajala, brisala ali spreminjala zbirke, temveč bo le poizvedovala po zbirki. UpamoHitrejša kot je poizvedba, bolje。
Primerjave skupnih množic
Pri opisovanju kompleksnosti algoritma se običajno uporabljajo o(1), o(n), o(logn), o(logn), o(nlogn), o(nlogn) za izražanje časovne zahtevnosti ustreznega algoritma, ki je izraz prostorsko-časovne zahtevnosti algoritma. Uporablja se ne le za predstavitev časovne kompleksnosti, temveč tudi za predstavitev prostorske kompleksnosti.
O sledi funkcija v oklepaju, ki označuje razmerje med časom/prostorom, ki ga porabi algoritem, in količino pridobljenih podatkov. kjer n predstavlja količino vhodnih podatkov.
Na primer, če je časovna zahtevnost O(n), to pomeni, da se količina podatkov poveča večkrat, prav tako pa se poraba časa večkrat poveča. Na primer, algoritmi pogostega premikanja. Drug primer je časovna zahtevnost O(n^2), kar pomeni, da ko se volumen podatkov poveča n-krat, traja čas, da se poveča n kvadratnih krat, kar je višja časovna zahtevnost kot linearna. Na primer, razvrščanje mehurčkov je tipičen algoritem O(n^2), ki ga je treba skenirati n × n krat, da se razvrsti n številk.
Drug primer je O(logn), ko se podatki povečajo n-krat, traja nekaj časa, da se logn časi povečajo (log tukaj temelji na 2, na primer, ko se podatki povečajo za 256-krat, se potreben čas poveča le za 8-krat, kar je manj kot linearno). Binarno iskanje je algoritem O (logn), ki vsakič, ko ga najdemo, izloči polovico možnosti, iskanje v 256 podatkih pa je treba najti le 8-krat, da se najde cilj.
O(nlogn) je enako, torej n pomnoženo z logn; ko se podatki povečajo za 256-krat, se poraba časa poveča za 256 x 8 = 2048-krat. Ta kompleksnost je višja od linearnosti pod kvadratom. Združevanje in sortiranje je časovna zahtevnost O(nlogn).
O(1) je najnižja prostorsko-časovna kompleksnost, torej čas/prostor, porabljen neodvisen od velikosti vhodnih podatkov; ne glede na to, kolikokrat se vhodni podatki povečajo, čas/prostor ostane nespremenjen. Algoritem zgoščevanja je tipična časovna zahtevnost O(1), ki lahko najde cilj po enem samem izračunu (ne glede na konflikte), ne glede na velikost podatkov.
Ta članek uporablja par BenchmarkDotNetList、HashSet、SortedSet、DictionaryZa poizvedbo za primerjalno analizo glejte naslednje:
Koda je naslednja:
Rezultat testa: Iskanje ključa v Dictionary ali HashSet je veliko hitreje kot iskanje v List in SortedSet. Časovna zahtevnost algoritmov Slovar in HashSet je O(1), in da bi prihranili pomnilnik, nam vrednost slovarja ni v pomoč, zato sem vseeno izbral shranjevanje HashSet.
|
Objavljeno na 7. 03. 2022 16:47:50
|
|
|
|
Objavljeno na 7. 03. 2022 23:09:48
|
Najemodajalec|
Objavljeno na 9. 03. 2022 09:55:12
|
