Reikalavimai: Turite apibrėžti tik skaitomo rinkinio tipą, kuris nepridės, neištrins ir nemodifikuos rinkinio, o tik pateiks užklausą rinkiniui. Tikimės, kadKuo greitesnė užklausa, tuo geriau。
Įprasti rinkinių palyginimai
Apibūdinant algoritmo sudėtingumą, o(1), o(n), o(logn), o(logn), o(nlogn) dažniausiai naudojami atitinkamo algoritmo laiko sudėtingumui išreikšti, kuris yra algoritmo erdvinio ir laiko sudėtingumo išraiška. Jis naudojamas ne tik laiko sudėtingumui pavaizduoti, bet ir erdviniam sudėtingumui pavaizduoti.
Po O skliausteliuose pateikiama funkcija, nurodanti santykį tarp algoritmo sunaudojamo laiko/erdvės ir surinktų duomenų kiekio. kur n reiškia įvesties duomenų kiekį.
Pavyzdžiui, jei laiko sudėtingumas yra O(n), tai reiškia, kad duomenų kiekis padidėja kelis kartus, o laiko sąnaudos taip pat padidėja kelis kartus. Pavyzdžiui, įprasti perėjimo algoritmai. Kitas pavyzdys yra laiko sudėtingumas O(n^2), o tai reiškia, kad kai duomenų kiekis padidėja n kartų, reikia laiko padidinti n kvadratinių kartų, o tai yra didesnis laiko sudėtingumas nei linijinis. Pavyzdžiui, burbulų rūšiavimas yra tipiškas O(n^2) algoritmas, kurį reikia nuskaityti n × n kartų, kad būtų galima rūšiuoti n skaičius.
Kitas pavyzdys yra O(logn), kai duomenys padidėja n kartų, reikia laiko padidinti prisijungimo laiką (žurnalas čia pagrįstas 2, pavyzdžiui, kai duomenys padidinami 256 kartus, reikalingas laikas padidėja tik 8 kartus, o tai yra mažesnis nei linijinis. Dvejetainė paieška yra O (logn) algoritmas, kuris pašalina pusę galimybių kiekvieną kartą, kai jis randamas, o 256 duomenų paiešką reikia rasti tik 8 kartus, kad būtų rastas taikinys.
O(nlogn) yra tas pats, tai yra, n padaugintas iš logn, kai duomenys padidinami 256 kartus, laiko sąnaudos padidėja 256 * 8 = 2048 kartus. Šis sudėtingumas yra didesnis nei tiesiškumas žemiau kvadrato. Sujungti ir rūšiuoti yra O(nlogn) laiko sudėtingumas.
O(1) yra mažiausias erdvės ir laiko sudėtingumas, tai yra, sunaudotas laikas/erdvė nepriklauso nuo įvesties duomenų dydžio, nesvarbu, kiek kartų įvesties duomenys padidinami, sunaudotas laikas/erdvė išlieka nepakitęs. Maišos algoritmas yra tipiškas O(1) laiko sudėtingumas, kuris gali rasti taikinį po vieno skaičiavimo (nepriklausomai nuo konfliktų), nesvarbu, kokio dydžio duomenys yra.
Šiame straipsnyje naudojama "BenchmarkDotNet" poraSąrašas、HashSet、SortedSet、ŽodynasLyginamosios analizės užklausa, žr.
Kodas yra toks:
Testo rezultatas: Rasti raktą žodyne arba maišų rinkinyje yra daug greičiau nei ieškoti sąraše ir SortedSet. Žodyno ir HashSet algoritmų laiko sudėtingumas yra O(1), o norint sutaupyti atminties, žodyno reikšmė mums nenaudinga, todėl vis tiek pasirinkau HashSet saugyklą.
|
Paskelbta 2022-03-07 16:47:50
|
|
|
|
Paskelbta 2022-03-07 23:09:48
|
Savininkas|
Paskelbta 2022-03-09 09:55:12
|
