728x90
반응형
복잡도
시간 복잡도
- 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
빅오 표기법
- 알고리즘의 로직이 얼마나 시간이 걸리는지(시간 복잡도)를 표현할 때 사용
- 입력 범위 n을 기준으로 로직의 반복 정도를 표시
- 가장 영향을 많이 미치는(=가장 큰) 항만 남김
시간 복잡도의 필요성
- 효율적인 코드 개선을 위해 필요
시간 복잡도의 속도 비교
공간 복잡도
- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
- 정적 변수와 동적 변수(재귀적 정의)를 모두 포함
자료구조에서의 시간 복잡도
[자료 구조의 평균 시간 복잡도]
자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
배열 (Array) | O(1) | O(n) | O(n) | O(n) |
스택 (Stack) | O(n) | O(n) | O(1) | O(1) |
큐 (Queue) | O(n) | O(n) | O(1) | O(1) |
이중 연결 리스트 (Doubly Linked List) | O(n) | O(n) | O(1) | O(1) |
해시 테이블 (Hash Table) | O(1) | O(1) | O(1) | O(1) |
이진 탐색 트리 (BST) | O(logn) | O(logn) | O(logn) | O(logn) |
AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
[자료 구조의 최악의 시간 복잡도]
자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
배열 (Array) | O(1) | O(n) | O(n) | O(n) |
스택 (Stack) | O(n) | O(n) | O(1) | O(1) |
큐 (Queue) | O(n) | O(n) | O(1) | O(1) |
이중 연결 리스트 (Doubly Linked List) | O(n) | O(n) | O(1) | O(1) |
해시 테이블 (Hash Table) | O(n) | O(n) | O(n) | O(n) |
이진 탐색 트리 (BST) | O(n) | O(n) | O(n) | O(n) |
AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
반응형
'코딩 테스트 > 파이썬 알고리즘' 카테고리의 다른 글
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제 (0) | 2024.03.07 |
---|---|
[코테 알고리즘] 파이썬 기본 / 관련 문제 (0) | 2024.03.07 |
[구버전] [Python] 04. 재귀 알고리즘 (0) | 2023.01.16 |
[구버전] [Python] 03. 스택과 큐 (0) | 2023.01.14 |
[구버전] [Python] 02. 검색 알고리즘 (0) | 2023.01.09 |