💡 복잡도
알고리즘의 성능을 나타내는 척도
시간 복잡도
특정 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지 = 연산 횟수 를 의미한다.
일반적으로 1초 = 1억번 의 연산을 의미한다.
시간 복잡도를 표현할 때는 빅오 (Big O) 표기법 을 사용한다.
위로 올라갈 수록 빠르다 !
O(1) : 상수
- 입력 데이터가 아무리 커져도 실행 시간 변화 X
- ex) 해시 테이블, 상수 연산
O(logN) : 로그
- 입력 데이터가 커져도 실행 시간 변화 크게 X
- 로그 함수 그래프처럼 x축 입력 데이터 커져도 y축 시간/공간 소모량은 완만하게 증가
- ex) 이진 검색 (binary search)
O(N) : 선형
- 입력 데이터 커지면 시간/메모리 저하
for,while반복문 -> 최소 O(N)
O(NlogN) : 로그 선형
- ex) 정렬 알고리즘
O(N^2) / O(N^3) : 2차 / 3차
- 2차 -> 입력 데이터 5배 늘어나면 실행 시간은 25배 늘어나는 ..
- 3차 -> 125배 ...
- ex) 이중 반복문, 삼중 반복문
서열
성능/효율 좋은 순 !
O(1) > O(log(n)) > O(n) > O(n * log(n)) > O(n^2) > O(n^3) > O(n^k) > O(k^n) > O(n!)설계
- N 의 범위가
500인 경우 : O(N^3) - N 의 범위가
2000인 경우 : O(N^2) - N 의 범위가
10,000인 경우 : O(NlogN) - N 의 범위가
10,000,000인 경우 : O(N)
공간 복잡도
특정 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
공간 복잡도를 표기할 때도 빅오 (Big O) 표기법 을 사용한다.
일반적인 int 형 자료형이 4Byte 라는 것을 가정했을 때, 배열 기준 크기는 다음과 같다.
- int arr[1000] : 4KB
- int arr[1000000] : 4MB
- int arr[1000][1000] : 4MB
- int arr[2000][2000] : 16MB
코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한 !
