Изисквания: Трябва да дефинирате тип колекция само за четене, която няма да добавя, изтрива или променя колекцията, а само да прави запитвания към колекцията. Надяваме сеКолкото по-бърза е заявката, толкова по-добре。
Често срещани сравнения на множества
При описване на сложността на алгоритъма, обикновено се използват o(1), o(n), o(logn), o(logn), o(nlogn) за изразяване на времевата сложност на съответния алгоритъм, който е изразът на пространствено-времевата сложност на алгоритъма. Използва се не само за представяне на времевата сложност, но и за представяне на пространствената сложност.
O е последвана от функция в скоби, която показва връзката между времето/пространството, използвано от алгоритъм, и количеството произведени данни. където n представлява количеството входни данни.
Например, ако времевата сложност е O(n), това означава, че количеството данни се увеличава няколко пъти, а времевата консумация също се увеличава няколко пъти. Например, често използвани алгоритми за преминаване. Друг пример е времевата сложност O(n^2), което означава, че когато обемът на данните се увеличи n пъти, отнема време да се увеличи n квадрат, което е по-висока времева сложност от линейното. Например, сортирането на балончета е типичен алгоритъм O(n^2), който трябва да бъде сканиран n × n пъти, за да се сортират n числа.
Друг пример е O(logn), когато данните се увеличават n пъти, отнема време да се увеличат логничните времена (логът тук е базиран на 2, например, когато данните се увеличат с 256 пъти, необходимото време се увеличава само 8 пъти, което е по-малко от линейното). Бинарното търсене е алгоритъмът на O (logn), който елиминира половината от възможностите всеки път, когато бъде намерено, а търсенето в 256 данни трябва да бъде намерено само 8 пъти, за да се намери целта.
O(nlogn) е същото, тоест n умножено по logn, когато данните се увеличат 256 пъти, времевата консумация се увеличава с 256 * 8 = 2048 пъти. Тази сложност е по-висока от линейността под квадрата. Merge and sorting е времевата сложност на O(nlogn).
O(1) е най-ниската пространствено-времева сложност, тоест времето/пространството, което се използва, е независимо от размера на входните данни, независимо колко пъти се увеличават, времето/пространството остава непроменено. Алгоритъмът за хеширане е типична O(1) времева сложност, която може да намери целта след едно изчисление (независимо от конфликтите), независимо колко големи са данните.
Тази статия използва двойката BenchmarkDotNetList、HashSet、SortedSet、DictionaryЗаявка за бенчмаркинг, вижте следното:
Кодът е следният:
Резултат от теста: Намирането на ключ в речник или хэшсет е много по-бързо, отколкото да търсите в списък и SortedSet. Времевата сложност на алгоритмите Dictionary и HashSet е O(1), и за да пестим памет, стойността на речника не ни е от полза, затова все пак избрах HashSet storage.
|
Публикувано в 7.03.2022 г. 16:47:50 ч.
|
|
|
|
Публикувано в 7.03.2022 г. 23:09:48 ч.
|
Хазяин|
Публикувано в 9.03.2022 г. 9:55:12 ч.
|
