Вимоги: потрібно визначити тип колекції лише для читання, який не додаватиме, видаляти чи змінювати колекцію, а лише звертатиме запити до колекції. Ми сподіваємосяЧим швидший запит, тим краще。
Поширені порівняння множин
При описі складності алгоритму зазвичай використовують o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) для вираження часової складності відповідного алгоритму, який є вираженням просторово-часової складності алгоритму. Вона використовується не лише для представлення часової складності, а й для представлення просторової складності.
Після O йде функція в дужках, яка вказує на взаємозв'язок між часом/простором, витраченим алгоритмом, і обсягом даних, які виробляються. де n позначає кількість вхідних даних.
Наприклад, якщо часова складність дорівнює O(n), це означає, що обсяг даних збільшується кілька разів, а також витрата часу кілька разів. Наприклад, поширені алгоритми обходу. Іншим прикладом є часова складність O(n^2), яка означає, що коли об'єм даних збільшується у n разів, потрібно час, щоб збільшити їх у n квадратних разів, що є складнішим за лінійність. Наприклад, сортування бульбашок — це типовий алгоритм O(n^2), який потрібно сканувати n × n разів для сортування n чисел.
Іншим прикладом є O(logn), коли дані збільшуються n разів, потрібно час, щоб збільшити час logn (журнал тут базується на 2, наприклад, коли дані збільшуються у 256 разів, необхідний час збільшується лише на 8 разів, що менше, ніж лінійний). Бінарний пошук — це алгоритм O (logn), який щоразу виключає половину можливостей при його знаходженні, а пошук у 256 даних потрібно знайти лише 8 разів, щоб знайти ціль.
O(nlogn) — це те саме, тобто n помножено на logn, і при збільшенні даних у 256 разів споживання часу збільшується на 256 * 8 = 2048 разів. Ця складність вища за лінійність нижче квадрата. Злиття та сортування — це часова складність O(nlogn).
O(1) — це найнижча просторово-часова складність, тобто витрачений час/простір не залежить від розміру вхідних даних, незалежно від того, скільки разів вхідні дані збільшувалися, витрачений час/простір залишається незмінним. Алгоритм хешування має типову часову складність O(1), яка може знайти ціль після одного обчислення (незалежно від конфліктів), незалежно від обсягу даних.
У цій статті використано пару BenchmarkDotNetList、HashSet、SortedSet、DictionaryЗапит для бенчмаркінгу, див. наступне:
Код виглядає так:
Результат тесту: Знайти ключ у словнику або хеш-сеті набагато швидше, ніж шукати у списку та SortedSet. Часова складність алгоритмів Dictionary і HashSet становить O(1), і для збереження пам'яті значення словника нам не допомагає, тому я все одно обрав HashSet storage.
|
Опубліковано 07.03.2022 16:47:50
|
|
|
|
Опубліковано 07.03.2022 23:09:48
|
Орендодавець|
Опубліковано 09.03.2022 09:55:12
|
