부트캠프를 다니면서 Big-O Notation을 배우게 되었는데
정리하지 않으면 추상적으로 머리에 남을 것 같아서 짧게 정리해보고자 한다.
🚨 올바르지 않은 내용이 있을 경우 댓글로 남겨주시면 감사드리겠습니다.
Big-O Notation이란?
Big-O Notation은 알고리즘의 성능, 효율성
즉 시간 및 공간 복잡도를 수학적으로 표기해주는 표기법이다.
즉 내가 만든 알고리즘이
(추상적으로) 시간이 얼마나 걸리는 지,
메모리 공간은 얼마나 필요한지를 나타내는 지표라고 생각하면 되겠다.
프로그래밍에서는 대체로 시간 복잡도를 더 중요하게 여기기 때문에 여기에서도 시간 복잡도에 대한 내용만 다루겠다.
그리고
Big-O는 알고리즘이 작업을 수행하는데까지 소요되는 정확한 시간(Running Time)을 표현하는 것이 아니다.
Big-O는 해당 알고리즘은 데이터(input)의 증가함에 따라
처리 시간이 얼마나 증가하는 지에 대한 패턴, 즉 증가율을 나타내는 개념이다.
여기서 데이터(input)는 Big-O Notation에서 n으로 표현된다.
(ex. O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!) ...)
Big-O Notation 참고 사항
Big-O 표기법 예시를 보기 전에 세 가지를 염두해야 한다.
1. Big-O 표기법은 영향력 없는 부분을 무시한다.
예를 들어, input에 따른 시간 증가의 변화가 실제로 3n²+2n+13이라고 해서
Big-O 표기가 O(3n²+2n+13)가 되지 않는다.
왜냐하면 Big-O 표기법은 input이 증가함에 따라
시간이 얼마나 증가하는 지에 대한 패턴, 증가율에 대한 표현에 포커스를 맞추기 때문이다.
3n²+2n+13에서 n² 앞의 상수 3과 뒤에 2n+13부분은 n이 증가하면 할 수록
시간 증가율에 미치는 영향이 미미하다.
따라서 위와 같은 부분은 Big-O 표기법에서 무시되고 O(n²)으로 표시된다.
2. Big-O 표기법은 보통 최악의 상황을 고려한다.
const example = [2,1,5,6,72,4,6,1,7,10,5,10];
function findTwo (arr) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === 2) return;
}
}
findTwo(example);
위 findTwo함수는 숫자 2를 찾기 위해서 for루프를 1번 밖에 돌지 않는다.
그럼에도 findTwo함수의 시간 복잡도는 O(n)이다.
왜냐하면 해당 함수에 들어어는 arr(input)에 따라 2가 제일 마지막 인덱스에 위치하여
끝까지 순회를 할 수 있기 때문이기도 하고, 2가 없으면 끝까지 순회해도 찾지 못할 경우가 있기 때문이다.
이것을 O(n) 런타임이라고 말하고, 일반적으로 Big-O 표기법은 "최악의 상황"을 내포한다.
(일반적이다 뿐이지 무조건이 아니다. Big-O를 평균으로 보는 관점도 있다.)
3. Big-O 표기할 때, Input(n)이 어떤 것을 의미하는 지 명확히 해야한다.
O(log n), O(n), O(n log n) 등 어떤 것을 표기하든지 간에 해당 코드에서 n이 의마하는 바가
무엇인지 정확하게 인지하고 있어야한다.
n 배열의 길이인지, 문자열의 길이인지, 탐색하고자 하는 노드의 개수인지를 파악해야
정확한 시간 복잡도를 표현할 수 있다. 위 2번의 예제 같은 경우 n은 배열의 길이이다.
Big-O Notation example
Big-O 표기법에 대해서 간단한 설명과 예시를 남기고자 한다.
1. O(1)
input의 크기에 상관없이 항상 같은 런타임이 소요됨을 의미한다.
function oOne(n) {
for (let i = 0; i < 1000; i++) {
console.log(n);
}
}위 코드는 함수에 전달되는 input의 크기과 관계없이 똑같은 횟수의 반복문을 순회한다.
따라서 위 코드의 시간복잡도는 O(1)이다.
흔히 O(1)이 가장 효율적인 구현이라고 생각을 하고(실제로도 그러한 경우가 많지만)
O(1)은 똑같은 런타임이 도출된다는 것을 보장할 뿐,
그 똑같은 런타임이 무조건 빠르다는 것을 표현하는 것은 아님을 명심해야한다.
즉, 매번 1초가 걸리는 지 매번 1년이 걸리는 지 O(1)만 보고서는 판단할 수가 없다는 것이다.
2. O(log N)
N의 크기에 log N만큼 런타임 시간이 증가함을 의미한다.
log N만큼이라고 하면 감이 잘 오지 않는다.
예시로는 Binary Search Tree(이진 탐색 트리)가 있다.
(편향 트리는 제외)
이진 탐색 트리는 간단하게 말하면
한 부모 노드에 왼쪽 오른쪽으로 자식 노드가 2개가 있는 형태이다.
왼쪽 자식 노드의 값은 부모 노드의 값보다 작고
오른쪽 자식 노드의 값은 부모 노드의 값보다 크다.
이진 탐색 트리에서 특정 값을 검색, 삽입, 삭제하기 위해서는
부모 노드에서부터 자식 노드까지 원하는 실행이 이루어질 때까지 1 depth씩 내려간다.
위 이진 탐색 트리를 예시를 들어, 111이란 값을 찾는 다고 가정해보자.
먼저 90에서 비교 후 오른쪽 자식 노드로 이동
150과 비교 후 왼쪽 자식 노드로 이동
95과 비교후 오른쪽 자식 노드로 이동
총 3번의 탐색 과정을 통해서 원하는 값을 찾았다.
노드의 개수 총 15개에 비해 적은 탐색 횟수이다.
만약 노드의 개수가 더 크다면?
만약 트리의 depth가 1 더 추가되어 2⁴의 노드 갯수가 더 추가된다고 하더라도
탐색 과정에서의 최악의 상황은 총 4번의 탐색을 하는 것이다.
위와 같이 N의 값은 빠르게 증가하지만
런타임이 증가하는 속도는 그에 비해 더디다는 것을 확인할 수 있다.(위 그래프를 참고)
즉
2^1(2개) => 1번 탐색
2^2(4개) => 2번 탐색
2^3(8개) => 3번 탐색
2^4(16개) => 4번 탐색 ... 이런식으로 진행된다.
결론적으로 O(logN)은 N이 크면 클수록 런타임의 증가율은 점점 줄어드는 시간복잡도라고 생각하면 되겠다.
(로그의 밑은 이진이기 때문에 2이다.)
수학적으로 왜 log n인지를 정확하게 알려면 해당 링크를 참조하면 되겠다.
3. O(N)
N의 크기에 따라 런타임 시간이 정비례하게 증가함을 의미한다.
function oN(n) {
for (let i = 0; i < n; i++) {
console.log(n);
}
}위 코드의 N이 Number타입이라고 가정할 경우, 전달되는 N의 크기 만큼 정비례하게 시간이 증가한다.
N이 10이라면 10을 순회하는 만큼의 시간이,
N이 10000000000라면 ,10000000000을 순회하는 만큼의 시간이 증가되어 소요된다.
3. O(Nlog N)
N의 크기에 따라 N log N의 런타임 시간이 정비례하게 증가함을 의미한다.
대표적인 예로는 정렬 로직중 합병 정렬(merge Sort)이 있다.
function mergeSort(nodes) {
if (nodes.length < 2) return nodes;
const sortedGroup = [];
const middle = Math.floor(nodes.length / 2);
const leftGroup = mergeSort(nodes.slice(0, middle));
const rightGroup = mergeSort(nodes.slice(middle));
while (leftGroup.length && rightGroup.length) {
if (leftGroup[0] > rightGroup[0]) {
sortedGroup.push(rightGroup.shift());
} else {
sortedGroup.push(leftGroup.shift());
}
}
while (leftGroup.length) sortedGroup.push(leftGroup.shift());
while (rightGroup.length) sortedGroup.push(rightGroup.shift());
return sortedGroup;
}합병 정렬은 정렬하고자하는 배열의 길이가 1 이하가 될 때가지
재귀적으로 배열을 반으로 나누어, 제자리를 찾아주는 정렬이다.
여기서 배열을 반으로 나누는 행위는
위에서 다룬 log N이라고 생각하면 된다.
그리고 다시 배열의 길이가 1이된 시점부터 각 요소들이 자신의 자리를 찾아가는데,
각 log N의 작업마다N개의 요소가 제자리로 가는 찾는 과정을 고려해야하기 때문에
log N 곱하기 N 즉 Nlog N이 된다.
여기서 합병 정렬이 어떻게 이루어지는 지 시각화 자료를 보면 이해에 도움이 될 것 같다.
4. O(N²)
N의 크기의 제곱만큼 런타임 시간이 증가함을 의미한다.
대표적인 예로 이중 for문이 있다.
function oNSquared(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(n);
}
}
}위 코드의 N이 Number타입이라고 가정할 경우, 전달되는 N의 제곱 크기 만큼 정비례하게 시간이 증가한다.
N이 3이라면, 9를 순회하는 만큼의 시간이,
N이 10이라면 ,100을 순회하는 만큼의 시간이 증가되어 소요된다.
이 외에도 O(2ⁿ), O(n!)등의 여러가지 시간복잡도 표현이 존재한다.
해당 예시에 대해서는 더 연구해보고 업데이트 할 예정이다.
결론
알고리즘의 시간복잡도를 표현하는 Big-O 표기법을 알게 되었다.
전에는 알고리즘 문제를 풀거나, 코드를 구현할 때 효율성에 대해서 추상적으로만 생각하였는데
앞으로 내가 구현하고자하는 코드가 어떠한 시간복잡도를 가지고 있는지,
또 어떻게 더 효율적인 코드로 개선할 수 있는지에 대한 방안도 꾸준히 연구해야겠다.
특히 자료구조 개념을 이용할 경우에는 내가 구현하는 자료구조의 Big-O가 어떤지에 대해서도 생각하면서 코드를 짜야겠다. http://bigocheatsheet.com/
