Követelmények: Olyan csak olvasható gyűjteménytípust kell definiálnod, amely nem adja, törli vagy módosítja a gyűjteményt, csak lekérdezi a gyűjteményt. Reméljük,Minél gyorsabb a lekérdezés, annál jobb。
Gyakori halmaz-összehasonlítások
Az algoritmus komplexitásának leírásakor, az o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) kifejezéseket gyakran használják a megfelelő algoritmus időkomplexitásának kifejezésére, amely az algoritmus tér-időbeli összetettségének kifejezése. Nemcsak az időbeli összetettség ábrázolására használják, hanem térbeli összetettség ábrázolására is.
Az O után egy zárójelben szereplő függvény jelzi, hogy az algoritmus által fogyasztott idő/tér és a felnőtt adatmennyiség közötti kapcsolat. ahol n a bemeneti adat mennyiségét jelenti.
Például, ha az idő bonyolultsága O(n), az azt jelenti, hogy az adatmennyiség többszörösösére nő, és az időfogyasztás is többszörösösére nő. Például gyakori áthaladási algoritmusok. Egy másik példa az O(n^2) időkomplexitás, ami azt jelenti, hogy amikor az adatmennyiség n-szeres nő, időbe telik, hogy n-négyzetszeres nőjön, ami magasabb időkomplexitás, mint a lineáris. Például a buborékrendezés tipikus O(n^2) algoritmus, amelyet n × n-szer kell beszkennelni n szám rendezéséhez.
Egy másik példa az O(logn), amikor az adatok n-szeresére nőnek, időbe telik a logn idők növelése (a log itt 2-re épül, például amikor az adatot 256-szor növeljük, az idő csak 8-szor nő, ami kevesebb, mint a lineáris). A bináris keresés az O (logn) algoritmusa, amely minden alkalommal a lehetőségek felét kizárja, és a 256 adatban végzett keresést csak 8-szor kell megtalálni, hogy megtaláljuk a célt.
O(nlogn) ugyanaz, vagyis n szorozva logn-nal, amikor az adatot 256-szorosával növeljük, az időfogyasztás 256 * 8 = 2048-szor nő. Ez a komplexitás magasabb, mint a lineáris szint a négyzet alatt. Az egyesítés és rendezés az O(nlogn) időkomplexitása.
O(1) a legalacsonyabb tér-időbeli komplexitás, vagyis a bemeneti adatok méretétől független az elfogyasztott idő/tér, függetlenül attól, hányszor növelik a bemeneti adatot, a felhasznált idő/tér változatlan marad. A hash-algoritmus tipikus O(1) időkomplexitás, amely egyetlen számítás után (függetlenül az ütközésektől) megtalálja a célpontot, függetlenül attól, mekkora az adat.
Ez a cikk a BenchmarkDotNet párt használjaList、HashSet、SortedSet、DictionaryBenchmarking lekérdezése a következőkre vonatkozik:
A kódex a következő:
Teszteredmény: Egy kulcs megtalálása egy szótárban vagy hashSetben sokkal gyorsabb, mint egy listában és a sortedSetben keresni. A Szótár és a HashSet algoritmusok időbeli összetettsége O(1), és a memória megtakarítása érdekében a Szótár értéke nem hasznos számunkra, ezért mégis a HashSet tárolást választottam.
|
Közzétéve 2022. 03. 07. 16:47:50
|
|
|
|
Közzétéve 2022. 03. 07. 23:09:48
|
Háziúr|
Közzétéve 2022. 03. 09. 9:55:12
|
