용어 | 정리 |
---|---|
공간복잡도 (space complexity) | 프로그램에서 필요한 메모리 자원 공간의 양 |
시간복잡도 (time complexity) | 프로그램이 수행하는 대입 이동 등의 연산들의 실행 횟수 여기에서 상수처럼 값이 변하지 않는 것은 무시되고 입력된 데이터만 고려됨 |
빅오(big 0) | 알고리즘 최적화에 크게 영향을 미치지 않는 부분을 무시해 간편하게 시간복잡도를 표기하는 방법 |
0(n^2) | 입력된 데이터값이 증가할 때 시간이 n의 제곱에 비례해 증가하는 복잡도를 가진 알고리즘 |
0(nlogn) | 분할 정복(conque÷)의 방식으로 탄생하게 된 병합 정렬에서 탄생한 방식으로 반으로 나누어 원소가 나눌 수 없을 때까지 반복하게되는 방식으로 logn을 n번 연산되는 방식 |
선택 정렬 (selection) | 가장 큰 or작은 값을 찾아서 선택하고 맨 처음 또는 맨 끝부터 차례대로 넣어주는 방식 시간복잡도는 n^2 공간복잡도는 n |
거품 정렬 (bubble) | 바로옆의 데이터와 비교해 정렬하는 행동을 반복하는 방식 |
합병 정렬 (merge) | 분할 정복(작은 단위로 쪼개서 해결하는 방식)을 사용하는 방식 nlogn의 시간복잡도와 n의 공간복잡도를 가짐 시간복잡도는 n^2 공간복잡도는 n |
퀵 정렬 (quick) | 분할 정복을 사용하는 방식으로 피벗값을 지정해 분할하는 과정을 추가함 평균적으로 nlogn의 시간 복잡도를 가지지만 최악의 상황에는n^2의 시간 복잡도를 가진다 공간복잡도는 n |