Wymagania: Musisz zdefiniować typ kolekcji tylko do odczytu, który nie będzie dodawał, usuwał ani nie modyfikował kolekcji, lecz jedynie zapytania do kolekcji. Mamy nadziejęIm szybciej zapytanie, tym lepiej。
Porównania zbiorów wspólnych
Opisując złożoność algorytmu, o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) są powszechnie używane do wyrażenia złożoności czasowej odpowiadającego algorytmu, która jest wyrazem złożoności przestrzenno-czasowej algorytmu. Używa się go nie tylko do reprezentowania złożoności czasowej, ale także do reprezentowania złożoności przestrzennej.
O jest poprzedzone funkcją w nawiasach, która wskazuje związek między czasem/przestrzenią zużywaną przez algorytm a ilością wyhodowanych danych. gdzie n oznacza ilość danych wejściowych.
Na przykład, jeśli złożoność czasowa wynosi O(n), oznacza to, że ilość danych wzrasta kilkukrotnie, a zużycie czasu również kilkakrotnie. Na przykład algorytmy powszechnego przechodzenia. Innym przykładem jest złożoność czasowa O(n^2), co oznacza, że gdy objętość danych wzrasta n razy, potrzeba czasu, aby zwiększyć n razy kwadratowych, co jest wyższą złożoność czasową niż liniowa. Na przykład sortowanie bąbelków to typowy algorytm O(n^2), który musi być skanowany n × n razy, aby uporządkować n liczb.
Innym przykładem jest O(logn), gdzie gdy dane rosną n razy, potrzeba czasu, aby zwiększyć czasy logn (log tutaj opiera się na 2, na przykład, gdy dane są zwiększone o 256 razy, czas potrzebny wzrasta tylko 8 razy, co jest mniej niż liniowe). Wyszukiwanie binarne to algorytm O (logn), który eliminuje połowę możliwości za każdym razem, gdy go znajdujemy, a wyszukiwanie w 256 danych wystarczy znaleźć 8 razy, aby znaleźć cel.
O(nlogn) jest tym samym, czyli n pomnożonym przez logn, gdy dane zwiększono o 256 razy, zużycie czasu wzrasta o 256 * 8 = 2048 razy. Ta złożoność jest wyższa niż liniowość poniżej kwadratu. Łączenie i sortowanie to złożoność czasowa O(nlogn).
O(1) to najniższa złożoność przestrzenno-czasowa, czyli czas/przestrzeń zużyta jest niezależna od rozmiaru danych wejściowych; niezależnie od tego, ile razy dane wejściowe są zwiększane, czas/przestrzeń pozostaje niezmieniona. Algorytm haszowania to typowa złożoność czasowa O(1), która może znaleźć cel po jednym obliczeniu (niezależnie od konfliktów), niezależnie od wielkości danych.
W tym artykule używa pary BenchmarkDotNetList、HashSet、SortedSet、SłownikZapytanie o benchmarking, odwołaj się do następujących:
Kod jest następujący:
Wynik testu: Znalezienie klucza w słowniku lub HashSetie jest znacznie szybsze niż wyszukiwanie w Liście i SortedSet. Złożoność czasowa algorytmów Słownika i HashSet wynosi O(1), a aby oszczędzać pamięć, wartość słownika nie jest dla nas użyteczna, więc nadal wybrałem pamięć HashSet.
|
Opublikowano 07.03.2022 16:47:50
|
|
|
|
Opublikowano 07.03.2022 23:09:48
|
Ziemianin|
Opublikowano 09.03.2022 09:55:12
|
