Požiadavky: Musíte definovať typ kolekcie len na čítanie, ktorý nebude pridávať, mazať ani meniť kolekciu, ale iba dotazovať kolekciu. Dúfame, žeČím rýchlejší dotaz, tým lepšie。
Porovnania spoločných množín
Pri popise zložitosti algoritmu sa bežne používajú o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) na vyjadrenie časovej zložitosti príslušného algoritmu, čo je vyjadrenie priestorovo-časovej zložitosti algoritmu. Používa sa nielen na reprezentáciu časovej zložitosti, ale aj na reprezentáciu priestorovej zložitosti.
O nasleduje funkcia v zátvorke, ktorá označuje vzťah medzi časom/priestorom spotrebovaným algoritmom a množstvom vypestovaných dát. kde n predstavuje množstvo vstupných údajov.
Napríklad, ak je časová zložitosť O(n), znamená to, že množstvo dát sa niekoľkonásobne zvýši a časová spotreba tiež niekoľkonásobne. Napríklad bežné algoritmy prechodu. Ďalším príkladom je časová zložitosť O(n^2), čo znamená, že keď sa objem dát zvýši n-násobne, trvá čas, kým sa zvýši n štvorcových krát, čo je vyššia časová zložitosť ako lineárna. Napríklad triedenie bublín je typický O(n^2) algoritmus, ktorý je potrebné prehľadať n × n krát, aby sa zoradilo n čísel.
Ďalším príkladom je O(logn), keď sa dáta zvýšia n-násobne, trvá čas, kým sa zväčšia logn-časy (logaritmis je tu založený na 2, napríklad keď sa dáta zvýšia o 256-násobok, potrebný čas sa zvýši len 8-násobne, čo je menej ako lineárne). Binárne vyhľadávanie je algoritmus O (logn), ktorý pri každom nájdení eliminuje polovicu možností, a vyhľadávanie v 256 dátach stačí nájsť 8-krát, aby sa našiel cieľ.
O(nlogn) je to isté, teda n vynásobené logn, keď sa dáta zvýšia 256-násobne, časová spotreba sa zvýši o 256 * 8 = 2048-násobok. Táto zložitosť je vyššia ako linearita pod štvorcom. Zlúčenie a triedenie je časová zložitosť O(nlogn).
O(1) je najnižšia priestorovo-časová zložitosť, teda čas/priestor spotrebovaný je nezávislý od veľkosti vstupných dát, bez ohľadu na to, koľkokrát sa vstupné údaje zvýšia, čas/priestor zostáva nezmenený. Hašovací algoritmus je typická časová zložitosť O(1), ktorá dokáže nájsť cieľ po jednom výpočte (bez ohľadu na konflikty), bez ohľadu na veľkosť dát.
Tento článok používa dvojicu BenchmarkDotNetList、HashSet、SortedSet、DictionaryPri vyhľadávaní benchmarkingu sa pozrite na nasledovné:
Kód je nasledovný:
Výsledok testu: Nájdenie kľúča v slovníku alebo hashsete je oveľa rýchlejšie ako vyhľadávanie v zozname a SortedSet. Časová náročnosť algoritmov Dictionary a HashSet je O(1) a aby sme šetrili pamäť, hodnota slovníka nám nepomáha, preto som stále zvolil úložisko HashSet.
|
Zverejnené 7. 3. 2022 16:47:50
|
|
|
|
Zverejnené 7. 3. 2022 23:09:48
|
Prenajímateľ|
Zverejnené 9. 3. 2022 9:55:12
|
