시간 복잡도

[C++] STL container 시간 복잡도 및 특징 비교

※용어 설명※ amortized : 분할 상환하다는 뜻을 가지고 있는 이 단어는, 쉽게 설명하자면 최악의 경우는 더 높은 값의 시간 복잡도를 가질 수 있지만, 대체적으로는~ 으로 생각하면 될 것 같다. 점근적 분석(Asymptotic analysis)으로 보면 O(n)이 나오는 경우에, 분할상환분석(Amortized Analysis)으로 보면 O(1)이 나오는 경우도 있기 때문이다. ​ red-black tree: 레드블랙트리. Balanced Binary-Search Tree로 이루어진 구조. [출처] C++ STL container 시간 복잡도 및 특징 비교.|작성자 Chan

시간 복잡도에 따른 알고리즘 목록

O(1) 배열 인덱스 접근 (예, arr[5];) 배열에 저장되있는 트리의 부모 또는 왼/오른쪽 자식 노드 검색 단일 연결 리스트에 노드를 삽입 이중 연결 리스트의 다음 또는 이전 요소에 접근 스택 푸시 팝 큐 삽입 삭제 해싱 (Hash Table) O(log n) 이중 탐색 이진 트리에서 최소 또는 최대값 검색 분할 정복 알고리즘 중 일차적인것들만 피보나치 수열 계산 O(n) 배열 순회 연결 리스트 순회 이진 검색 정렬이 되어있지 않은 연결 리스트 요소 제거 두 문자열간 비교 회문인지 검사 계수/버킷 정렬 O(n log n) 병합 정렬 힙 정렬 퀵 정렬 분할 정복 알고리즘 중 O(n^2)로 구현되있는것들 O(n^2) 버블 정렬 삽입 정렬 선택 정렬 단순한 2차원 배열 순회 O(n!) 브루트포스 탐색 방..