알고리즘 (Algorithm)

• 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것

• 프로그래밍에서 알고리즘은 input 값을 통해 output 값을 얻기 위한 계산 과정

조건

• 입력(Input) : 외부에서 주어지는 자료는 0개 이상
• 출력(Output) : 적어도 2개 이상의 서로 다른 결과를 출력
• 명확성(Definiteness) : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 함
• 유한성(Finiteness) : 유한한 시간 내 혹은 유한한 회수 후에 종료
• 효율성(수행가능성, Efficiency) : 모든 과정은 명백하게 실행 가능(검증 가능) 해야함

좋은 알고리즘의 기준

• 정확성 : 입력에 대해 유한 시간 내에 올바른 답을 산출하는가
• 작업량 : 가장 중요한 연산의 작업량 측정, 여러 개인 경우 합 또는 - 가중치를 부여하여 계산
• 기억 장소 사용량 : 수행에 필요한 저장 공간 ( 공간적 비용 )
• 복잡도 : 알고리즘이 소모하는 소요 시간(시간 복잡도)과 메모리 사용량(공간 복잡도) 등의 자원 ( 시간적 비용 )
• 최적성 : 더 적은 연산으로 수행 가능한 알고리즘이 있는가

# 복잡도

시간 복잡도
n 크기의 입력량을 처리하는데 필요한 연산의 횟수
- 현실에서 통용되는 상한선은 O( n log n ) 까지

공간 복잡도
n 크기의 입력량을 처리하는데 필요한 작업 기억 영역(메모리)의 양
- 현실에서 통용되는 상한선은 3차원( i*j*k, ..., n^3 ) 까지

시간 복잡도의 점근적 표기법

• 빅-오(Big-O) : 상한 (Upper bound)
• 빅-오메가(Big-Ω) : 하한 (Lower bound)
• 빅-세타(Big-θ) : 평균 (상한과 하한이 같을 때)

표기법	작동 방식	종류
O(1)	입력값에 상관없이 문제해결 시간이 일정함 (상수 복잡도)	해시 테이블
O(log n)	입력값에 따른 문제해결 시간이 크게 변하지 않음 (대수 복잡도)	이진 탐색
O(n)	입력값과 문제해결 시간이 1:1 관계 (선형 복잡도)	정렬되지 않은 배열에서의 탐색
O(n log n)	문제해결 시간이 짧은 알고리즘을 입력값만큼 수행 (선형 대수 복잡도)	퀵 정렬, 병합 정렬, 힙 정렬
O(n^2)	입력값에 비례하고, 실행 횟수에 따라 문제해결 시간이 증가 (2차 복잡도)	이중 for문, 삽입 정렬, 선택 정렬, 버블 정렬
O(n^3)	(3차 복잡도)	행렬 곱셉(n*m)
O(2^n)	입력값에 따라 문제해결 시간이 기하급수 적으로 증가 (기하급수 복잡도, 지수 복잡도)	완전탐색, 피보나치 수열
O(n!)	팩토리얼 복잡도	완전탐색 무작위대입

---

자료 구조에 따른 시간 복잡도

---

출처 : 사진 클릭 시 이동