Cerințe: Trebuie să definești un tip de colecție doar pentru citire, care nu va adăuga, șterge sau modifica colecția, ci va interoga doar colecția. SperămCu cât interogarea este mai rapidă, cu atât mai bună。
Comparații comune de mulțimi
Când se descrie complexitatea algoritmului, o(1), o(n), o(logn), o(logn), o(nlogn) sunt folosite frecvent pentru a exprima complexitatea temporală a algoritmului corespunzător, care este expresia complexității spațiotemporale a algoritmului. Este folosit nu doar pentru a reprezenta complexitatea temporală, ci și pentru a reprezenta complexitatea spațială.
O este urmat de o funcție între paranteze care indică relația dintre timpul/spațiul consumat de un algoritm și cantitatea de date crescute. unde n reprezintă cantitatea de date de intrare.
De exemplu, dacă complexitatea de timp este O(n), înseamnă că cantitatea de date crește de mai multe ori, iar consumul de timp crește de asemenea de mai multe ori. De exemplu, algoritmi comuni de traversare. Un alt exemplu este complexitatea de timp O(n^2), ceea ce înseamnă că atunci când volumul de date crește de n ori, durează timp să crești de n ori pătrate, ceea ce este o complexitate de timp mai mare decât liniar. De exemplu, sortarea bulelor este un algoritm tipic O(n^2), care trebuie scanat de n × n ori pentru a sorta n numere.
Un alt exemplu este O(logn), când datele cresc de n ori, durează timp să crească logn (logul de aici se bazează pe 2, de exemplu, când datele sunt mărite cu 256 de ori, timpul necesar crește doar de 8 ori, ceea ce este mai mic decât liniar). Căutarea binară este algoritmul lui O (logn), care elimină jumătate din posibilități de fiecare dată când este găsită, iar căutarea din 256 de date trebuie găsită de doar 8 ori pentru a găsi ținta.
O(nlogn) este același, adică n înmulțit cu logn; când datele sunt mărite cu 256 de ori, consumul de timp crește cu 256 * 8 = 2048 de ori. Această complexitate este mai mare decât liniaritatea sub pătrat. Fuziunea și sortarea reprezintă complexitatea temporală a lui O(nlogn).
O(1) este cea mai mică complexitate spațiotemporală, adică timpul/spațiul consumat este independent de dimensiunea datelor de intrare, indiferent de câte ori sunt mărite datele de intrare, timpul/spațiul consumat rămâne neschimbat. Algoritmul de hashing are o complexitate tipică de timp O(1), care poate găsi ținta după un singur calcul (indiferent de conflicte), indiferent cât de mari sunt datele.
Acest articol folosește perechea BenchmarkDotNetList、HashSet、SortedSet、DictionaryPentru consultarea benchmarking, consultați următoarele:
Codul este următorul:
Rezultatul testului: Găsirea unei chei pe un dicționar sau un hashset este mult mai rapidă decât căutarea într-un List și SortedSet. Complexitatea de timp a algoritmilor Dictionary și HashSet este O(1), iar pentru a economisi memorie, valoarea Dictionary-ului nu ne este de folos, așa că am ales totuși stocarea HashSet.
|
Postat pe 07.03.2022 16:47:50
|
|
|
|
Postat pe 07.03.2022 23:09:48
|
Proprietarul|
Postat pe 09.03.2022 09:55:12
|
