복잡도

복잡도?
알고리즘이 실행함에 있어, 문제의 크기 (일반적으로 데이터 원소의 개수를 뜻합니다) 가 커짐에 따라서 얼마나 큰 시간을 (또는 공간을) 요구하는지를 뜻하는 것.

시간복잡도
: 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 시간이 어떤 양상으로 증가하는가
공간복잡도
: 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 기억 공간 (메모리) 의 필요가 어떤 양상으로 증가하는가

Big O?
알고리즘의 복잡도를 표현하는 점근 표기법(asymptotic notation)중, 가장 많이 쓰이는 기법.

O(1) - 상수시간
: 문제를 해결하는데 오직 한 단계로 끝남. - 해시테이블 추가, 배열에서 특정 인덱스 찾기

O(log n) - 로그시간
: 문제해결시, 특정 요인으로 인해 시간이 줄어듬. - 이진(binary)탐색

O(n) - 직선시간
: 문제를 해결하기위한 단계의 수와 입력 값(n)이 1:1관계를 가짐. - 연결리스트(linked list)

O(n log n) - 선형로그형
: 데이터수가 2배 증가시, 연산횟수도 2배 넘게 증가 - 퀵(quick)정렬, 병합(merge)정렬

O(n^) - 2차시간
: 문제를 해결하기위한 단계의 수가 n의제곱

O(2^n) - 지수시간
: 문제를 해결하기위한 단계의 수가 2의 n제곱

출처:
(번역) 알고리즘 쉽게 이해하기 : 시간 복잡도와 Big-O 표기
복잡도(Complexity) : 시간 복잡도
출처: 프로그래머스 강의 "어서와! 자료구조와 알고리즘은 처음이지?"