Nõuded: Pead määratlema ainult lugemiseks mõeldud kogutüübi, mis ei lisa, kustuta ega muuda kogu, vaid ainult päringuid kogule. LoodameMida kiirem on päring, seda parem。
Levinud komplektide võrdlused
Algoritmi keerukuse kirjeldamisel kasutatakse tavaliselt o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) vastava algoritmi ajakomplekssuse väljendamiseks, mis on algoritmi ruumi-aja keerukuse väljendus. Seda kasutatakse mitte ainult ajalise keerukuse esindamiseks, vaid ka ruumilise keerukuse esindamiseks.
O-le järgneb sulgudes olev funktsioon, mis näitab seost algoritmi tarbitava aja/ruumi ja kasvatatud andmemahu vahel. kus n tähistab sisendandmete hulka.
Näiteks, kui ajakompleksus on O(n), tähendab see, et andmete hulk suureneb mitu korda ja ajatarbimine samuti mitu korda. Näiteks levinud liikumisalgoritmid. Teine näide on ajakeerukus O(n^2), mis tähendab, et kui andmemaht suureneb n korda, võtab aega, et kasvada n ruutkorda, mis on ajakeerukus suurem kui lineaarne. Näiteks mullisorteerimine on tüüpiline O(n^2) algoritm, mida tuleb skaneerida n × n korda, et sorteerida n arvu.
Teine näide on O(logn), kus kui andmed suurenevad n korda, võtab logn-aegade suurendamine aega (logi põhineb siin 2-l, näiteks kui andmeid suurendatakse 256 korda, suureneb vajalik aeg vaid 8 korda, mis on väiksem kui lineaarne). Binaarne otsing on O (logn) algoritm, mis kõrvaldab poole võimalustest iga kord, kui see leitakse, ning 256 andme otsingut tuleb leida vaid 8 korda, et leida sihtmärk.
O(nlogn) on sama, st n korrutatud logniga, kui andmeid suurendada 256 korda, suureneb ajatarbimine 256 * 8 = 2048 korda. See keerukus on suurem kui lineaarsus ruudu all. Ühendamine ja sorteerimine on O(nlogn) ajakeerukus.
O(1) on madalaim ruumi-aja keerukus, see tähendab, et tarbitav aeg/ruum ei sõltu sisendandmete suurusest, ükskõik kui mitu korda sisendandmeid suurendatakse, tarbitav aeg/ruum jääb muutumatuks. Räsi algoritm on tüüpiline O(1) ajakeerukus, mis suudab sihtmärgi leida pärast ühte arvutust (sõltumata konfliktidest), olenemata andmete suurusest.
See artikkel kasutab BenchmarkDotNet paariList、HashSet、SortedSet、DictionaryVõrdlusuuringute päring viitab järgmistele:
Kood on järgmine:
Testitulemus: Võtme leidmine sõnastikust või hashSetist on palju kiirem kui loendist ja sortedSetist otsimine. Sõnastiku ja HashSeti algoritmide ajakeerukus on O(1) ning mälu säästmiseks pole Sõnastiku Väärtus meile kasulik, seega valisin ikkagi HashSeti salvestuse.
|
Postitatud 07.03.2022 16:47:50
|
|
|
|
Postitatud 07.03.2022 23:09:48
|
Üürileandja|
Postitatud 09.03.2022 09:55:12
|
