요구사항: 컬렉션을 추가, 삭제, 수정하지 않고 컬렉션만 쿼리하는 읽기 전용 컬렉션 타입을 정의해야 합니다. 우리는 희망합니다쿼리가 빠를수록 좋습니다。
일반적인 집합 비교
알고리즘의 복잡도를 설명할 때, o(1), o(n), o(logn), o(logn), o(logn), o(nlogn), 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) 시간 복잡도를 가지며, 데이터가 아무리 크더라도 단일 계산(충돌 여부와 상관없이) 목표를 찾을 수 있습니다.
이 글에서는 BenchmarkDotNet 쌍을 사용합니다List, HashSet, SortedSet, 사전(Dictionary)벤치마킹 문의는 다음을 참고하세요:
코드는 다음과 같습니다:
테스트 결과: 사전이나 해시셋에서 키를 찾는 것이 리스트나 정렬셋에서 찾는 것보다 훨씬 빠릅니다. Dictionary와 HashSet 알고리즘의 시간 복잡도는 O(1)이며, 메모리를 절약하기 위해 Dictionary의 값은 우리에게 쓸모가 없으므로 저는 여전히 HashSet 저장소를 선택했습니다.
|
게시됨 2022. 3. 7. 오후 4:47:50
|
|
|
|
게시됨 2022. 3. 7. 오후 11:09:48
|
집주인|
게시됨 2022. 3. 9. 오전 9:55:12
|
