효율적인 알고리즘이란
주어진 문제를 해결하는 과정을 최소한의 자원(시간과 공간)을 사용하여 수행하는 알고리즘을 말합니다.
👉시간 복잡도 (Time Complexity)
문제를 해결하는데 걸리는 시간과 입력의 함수 관계이며
효율적인 코드로 개선하는 데 쓰이는 척도 가 됩니다.
👉공간 복잡도 (Space Complexity)
프로그램을 실행시키거나 알고리즘의 실행에 사용되는 자원(메모리)공간의 양 을 말합니다.
일반적인 int 형 자료형이 4Byte라는 것을 가정했을 때, 배열 기준 크기는 다음과 같습니다.
int arr[1000] : 4byte * 1000 = 4KB
int arr[1000000] : 4byte * 10^6 = 4MB
int arr[1000][1000] : 4byte * 10^6 = 4KB
int arr[2000][2000] : 4*10^6 * 4byte = 16*10^6byte =16MB 보통 100만개 이상의 배열을 선언하는 경우는 드물기 떄문에 알고리즘 설계를 제대로 하고 있는지 점검이 필요합니다.
👉빅오 표기법 (Big-O Notation)
알고리즘의 시간복잡도나 공간 복잡도를 표현하는 수학적인 표기법 중 하나입니다. 알고리즘의 성능을 비교하거나 분석하기 위해 사용되며, 입력 크기에 대한 알고리즘의 시간 또는 메모리 사용량의 상한을 나타냅니다.
빅오 표기법의 크기와 성능 비교
O(N!) > O(2^n) > O(N²) > O(N log N) > O(N) > O(Log N) > O(1)
- O(1) - 상수 시간 : 입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는 데 오직 한 단계만 거침.
- O(log n) - 로그 시간 : 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦.
- O(n) - 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값이 1:1 관계를 가짐.
- O(n^2) - 2차 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n의 제곱.
- O(C^n) - 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 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 liked 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 liked 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) |
알고리즘+자료구조, CS지식 정리
좋은 정보 감사합니다