알고리즘이란
어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야하는 일련의 과정들을 의미한다.
가는 루트는 다양하며 여러가지 상황에 따른 알고리즘은 모두 다르다. 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.
알고리즘의 실행 부분을 두 부분으로 나누면
- 입력값의 크기에 따라 알고리즘의 실행시간을 검증해볼 수 있다.
- 입력값의 크기에 따른 함수의 증가량, 이것을 성장률이라고 부른다.
이때 중요하지 않은 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데 이것을 점근적 표기법이라고 부른다.
여기서 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미이다.
점근적 표기법은 다음 세가지가 있는데 시간 복잡도를 나타내는데 사용한다.
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
평균인 세타 표기를 하면 가장 정확하고 좋겠지만 평가하기 까다롭다.
그래서 최악인 경우인 빅오를 사용하는데 알고리즘이 최악일때의 경우를 판단하면 평군과 가까운 성능으로 예측하기 쉽다.
Big-O 표기법
빅오 표기법 : 알고리즘의 최악의 경우 복잡도
빅오 표기법에서 n은 입력의 개수를 의미한다.
즉, 알고리즘을 구현 할 때 빅오 표기법이 해당 알고리즘이 얼마나 효율적인지 나타낸다.
Big-O로 측정되는 복잡성에는 시간과 공간 복잡도가 있다.
시간 복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
공간 복잡도 : 알고리즘이 실행될때 사용하는 메모리의 양을 나타낸다.
요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아졌다
시간복잡도
일반적인 예
O(1)은 입력 공간에 대해 변하지 않는다. 따라서 상수시간이라 부른다.
배열에 있는 항목을 인덱스를 사용해 접근하는 경우가 O(1)알고리즘의 예이다.
O(n)알고리즘의 예로 다음코드와 같이 0부터 n-1까지의 숫자를 출력하는 경우가 있다.
function exampleLinear(n) {
for(let i = 0 ; i < n; i++){
console.log(i);
}
} 마찬가지로 O(n 2 )은 2차 시간이고 O(n 3 )은 3차 시간이다.
시간복잡도의 예는 다음과 같다.
function exampleQuadratic(n) {
for(let i = 0 ; i < n; i++){
console.log(i);
for(let j = 0 ; j < n; j++){
console.log(j);
}
}
} function exampleCubic(n) {
for(let i = 0 ; i < n; i++){
console.log(i);
for(let j = 0 ; j < n; j++){
console.log(j);
for(let k = 0 ; k < n; k++){
console.log(k);
}
}
}
} 마지막으로 로그 시간 복잡도를 지닌 알고리즘의 예로는 2의 2승부터 n승까지의 항목을 출력하는 경우가 있다.
예를 들어 exampleLogarithmic(10)은 다음 결과를 출력한다.
2,4,8,16,32,64로그 시간 복잡도의 효율은 백만개의 항복과 같이 큰 입력이 있는 경우 효율적이다. n이 백만이라고 하더라도 log2(1,000,000)=19.93xxx이기 때문에 단지 19개의 항목만 출력한다.
function exampleLogarithmic(n){
for(let i = 2; i <= n; i= i*2){
console.log(i);
}
}
정리하자면
O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
빅오 표기법 규칙
-
계수 법칙 (상수를 제거하라.)
입력크기 n과 관련되지 않은 계수를 제거한다. n이 무한에 가까워지는 경우 다른 계수는 무시해도 되기 때문이다. -
합의 법칙 (빅오를 더하라.)
f(n)이 O(h(n))이고 g(n)이 O(p(n))이면 f(n)+g(n)은 O(h(n)+p(n))이다.
-
곱의 법칙 (빅오를 곱하라.)
곱의 법칙은 합의 법칙과 마찬가지고 두개의 다른 시간 복잡도를 곱할때, 빅오 표기법 역시 곱해진다. -
전이 법칙 (교환 법칙)
f(n)이 O(g(n))이고 g(n)이 O(h(n))이면 f(n)은 O(h(n)) 이다.
교환 법칙은 동일한 시간 복잡도는 동일한 빅오 표기법을 지님을 나타내기 위한 간단한 방법이다. -
다항 법칙 (빅오의 k제곱)
f(n)이 k차 다항식이면 f(n)은 O(nk) 이다.
시간 복잡도를 구하는 요령
각 문제의 시간 복잡도 유형을 빨리 파악할 수 있도록 아래의 예를 통해 빠르게 알아 볼 수 있다.
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O(n)
- 컬렉션의 절반 이상을 반복하는 경우 : O(n/2) -> O(n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
참고
