Prasības: Jums ir jādefinē tikai lasāmas kolekcijas tips, kas nepievienos, neizdzēsīs vai nemodificēs kolekciju, bet tikai vaicās kolekciju. Mēs ceramJo ātrāks vaicājums, jo labāk。
Bieži sastopamie kopu salīdzinājumi
Aprakstot algoritma sarežģītību, o(1), o(n), o(logn), o(logn), o(nlogn) parasti tiek izmantoti, lai izteiktu attiecīgā algoritma laika sarežģītību, kas ir algoritma telpiskās un laika sarežģītības izpausme. To izmanto ne tikai, lai attēlotu laika sarežģītību, bet arī telpisko sarežģītību.
O seko funkcija iekavās, kas norāda attiecību starp algoritma patērēto laiku/telpu un iegūto datu apjomu. kur n apzīmē ievades datu apjomu.
Piemēram, ja laika sarežģītība ir O(n), tas nozīmē, ka datu apjoms palielinās vairākas reizes, un arī laika patēriņš palielinās vairākas reizes. Piemēram, parastie šķērsošanas algoritmi. Vēl viens piemērs ir laika sarežģītība O(n^2), kas nozīmē, ka, palielinoties datu apjomam n reizes, ir nepieciešams laiks, lai palielinātu n kvadrātreizes, kas ir lielāka laika sarežģītība nekā lineārā. Piemēram, burbuļu kārtošana ir tipisks O(n^2) algoritms, kas jāskenē n × n reizes, lai kārtotu n skaitļus.
Vēl viens piemērs ir O(logn), kad dati palielinās n reizes, ir nepieciešams laiks, lai palielinātu logn laikus (žurnāls šeit ir balstīts uz 2, piemēram, ja dati tiek palielināti par 256 reizēm, nepieciešamais laiks palielinās tikai par 8 reizēm, kas ir mazāks par lineāro. Binārā meklēšana ir O (logn) algoritms, kas katru reizi, kad tas tiek atrasts, novērš pusi no iespējām, un meklēšana 256 datos ir jāatrod tikai 8 reizes, lai atrastu mērķi.
O(nlogn) ir vienāds, tas ir, n reizināts ar logn, kad dati tiek palielināti par 256 reizēm, laika patēriņš palielinās par 256 * 8 = 2048 reizes. Šī sarežģītība ir augstāka nekā linearitāte zem kvadrāta. Sapludināt un kārtot ir O(nlogn) laika sarežģītība.
O(1) ir zemākā telpiskā laika sarežģītība, tas ir, patērētais laiks/telpa ir neatkarīga no ievades datu lieluma, neatkarīgi no tā, cik reižu ievades dati tiek palielināti, patērētais laiks/telpa paliek nemainīga. Jaukšanas algoritms ir tipiska O(1) laika sarežģītība, kas var atrast mērķi pēc viena aprēķina (neatkarīgi no konfliktiem), neatkarīgi no tā, cik lieli ir dati.
Šajā rakstā tiek izmantots BenchmarkDotNet pārisSaraksts、HashSet、SortedSet、VārdnīcaVaicājums salīdzinošai novērtēšanai, skatiet sekojošo:
Kods ir šāds:
Testa rezultāts: Atslēgas atrašana vārdnīcā vai HashSet ir daudz ātrāka nekā meklēšana sarakstā un SortedSet. Vārdnīcas un HashSet algoritmu laika sarežģītība ir O(1), un, lai ietaupītu atmiņu, vārdnīcas vērtība mums nav noderīga, tāpēc es joprojām izvēlējos HashSet krātuvi.
|
Publicēts 07.03.2022 16:47:50
|
|
|
|
Publicēts 07.03.2022 23:09:48
|
Saimnieks|
Publicēts 09.03.2022 09:55:12
|
