Požadavky: Musíte definovat typ kolekce pouze pro čtení, který nebude přidávat, mazat ani upravovat kolekci, ale pouze dotazovat kolekci. DoufámeČím rychlejší dotaz, tím lépe。
Porovnání společných množin
Při popisu složitosti algoritmu se běžně používají o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) k vyjádření časové složitosti odpovídajícího algoritmu, což je vyjádření prostorově-časové složitosti algoritmu. Používá se nejen k reprezentaci časové složitosti, ale také k zobrazení prostorové složitosti.
O je následováno funkcí v závorce, která ukazuje vztah mezi časem/prostorem spotřebovaným algoritmem a množstvím vypěstovaných dat. kde n představuje množství vstupních dat.
Například pokud je časová složitost O(n), znamená to, že množství dat se několikanásobně zvyšuje a časová spotřeba také několikanásobně. Například běžné algoritmy pro procházení. Dalším příkladem je časová složitost O(n^2), což znamená, že když se objem dat zvýší nkrát, trvá čas, než se zvýší n čtverečníkrát, což je vyšší časová složitost než lineární. Například třídění bublin je typický algoritmus O(n^2), který je třeba prohledat n × n krát, aby seřadil n čísel.
Dalším příkladem je O(logn), když se data zvýší nkrát, trvá nějaký čas, než se logn časy zvýší (logaritmis zde je založen na 2, například když se data zvýší o 256násobek, potřebná doba se zvýší jen 8krát, což je méně než lineární). Binární vyhledávání je algoritmus O (logn), který při každém nalezení eliminuje polovinu možností, a hledání v 256 datech stačí najít 8krát, aby se našel cíl.
O(nlogn) je totéž, tedy n vynásobené logn, když se data zvýší 256krát, časová spotřeba se zvýší o 256 * 8 = 2048krát. Tato složitost je vyšší než linearita pod druhou mocnou. Sloučení a třídění je časová složitost O(nlogn).
O(1) je s nejnižší prostorově-časovou složitostí, tedy čas/prostor spotřebovaný je nezávislý na velikosti vstupních dat, bez ohledu na to, kolikrát se vstupní data zvýší, čas/prostor zůstává nezměněn. Hašovací algoritmus je typická časová složitost O(1), která dokáže najít cíl po jediném výpočtu (bez ohledu na konflikty), bez ohledu na velikost dat.
Tento článek používá dvojici BenchmarkDotNetList、HashSet、SortedSet、DictionaryDotaz na benchmarking viz následující:
Kód je následující:
Výsledek testu: Nalezení klíče ve slovníku nebo Hashsetu je mnohem rychlejší než hledání v seznamu a SortedSetu. Časová složitost algoritmů Slovník a HashSet je O(1) a abychom šetřili paměť, hodnota slovníku nám není k ničemu, proto jsem stále zvolil úložiště HashSet.
|
Zveřejněno 07.03.2022 16:47:50
|
|
|
|
Zveřejněno 07.03.2022 23:09:48
|
Pronajímatel|
Zveřejněno 09.03.2022 9:55:12
|
