알고리즘의 성능과 빅 오 표기법

1. 알고리즘 (algorithm)
알고리즘이란 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 의미한다. 알고리즘(algorithm)의 어원은 9세기 페르시아의 수학자인 무하마드 알콰리즈미(Muhammad al-Kwarizmi)의 이름을 라틴어화한 algorismus에서 따온 말이다.

- 성능(시간복잡도)과 빅-오 표기법(Big-O Notation)
복잡한 알고리즘일수록 성능을 정확하게 계산하기란 매우 어려운 일이다. 따라서 알고리즘이 복잡할 때 전체 수행 시간에 큰 영향을 미치는 부분만을 고려하여 보다 직관적으로 성능을 추정하고, 표현할 필요가 있다. 이런 경우에 일반적으로 빅-오 표기법(Big-O Notation)을 많이 사용한다.

빅-오 표기법(Big-O Notation)이란 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 생략하는 표기법이다. 입으로 소리내어 읽을 때 O는 order라고 읽는다. O(n²)은 order and 제곱이라고 읽는다. 빅-오 표기법에 따라 주요 알고리즘의 속도는 하기와 같이 표현된다.

O(1)       : 상수적 (배열의 원소 접근, 단순 명령문)
O(lg(n))   : 대수적 (이진 검색) [lg(n)은 log₂(n)의 줄인 표현]
O(n)       : 선형적 (순차 검색)
O(nlg(n)) : 선형적보다는 좋지 않음. (퀵 정렬과 힙 정렬의 평균 수행 시간)
O(n²)      : 제곱적 (선택 정렬과 삽입 정렬)
O(n³)      : 세제곱적 (두 n x n 행렬의 곱)
O(Cⁿ)      : 지수적 (여행하는 판매원 문제, 집합 분할)
* n → 입력의 크기

반복문의 수행 횟수는 알고리즘의 성능과 직결된다.빅-오 표기법에 나타나는 알고리즘 성능 추정도 반복문의 수행 횟수를 기반으로 한다. 뛰어난 성능을 자랑하는 이진 탐색은 정렬되어 있는 특징을 이용하여, 약 43억개의 원소가 있는 리스트에서 특정 값을 찾아낼 때 최악의 경우에도 32회면 원하는 값을 찾아낼 수 있다.

일반적인 정렬 알고리즘에 대하여는 하기 페이지에 정리되어있다.
https://mrnamu.blogspot.com/2019/10/1-bubble-sort-insert-sort.html
https://mrnamu.blogspot.com/2019/10/2-quick-sort-merge-sort-binary-search.html