✔️빅오 표기법 (big-O notation)이란?
- 알고리즘의 성능을 분석, 비교하기 위한 개념 중 하나입니다.
- 보통 알고리즘의 시간 복잡도와 공간 복잡도를 예측에 사용 됩니다.
- 점근적 표현법 중 하나로, 일반적으로 상수와 계수를 제거하고 알고리즘의 복잡도를 단순화 하여 나타냅니다.
- 애매해 질 수도 있는 연산 횟수 계산법을 하나의 일관된 형식으로 만들어 줍니다.
- 알고리즘의 런 타임이 인풋의 증가에 따라서 어떻게 함께 증가 하는지에 대해 설명 할 수 있게 해줍니다.
✔️정리하면
빅오 표기법은 알고리즘의 직접적인 모든 연산 횟수를 계산하는것이 아닌,
인풋의 증가에 따른 연산 처리시간의 증가율을 예측하는 척도입니다.
✔️공간 복잡도(Space complexity)가 뭐지?
프로그램이 실행되고 완료되기까지 사용하는 총 저장 공간량을 의미한다.
- 저장 공간에는
고정 공간과가변 공간으로 나뉜다.- 고정 공간 - 알고리즘과는 관련 없는 공간으로 코드와 단순 변수, 상수가 해당된다.
- 가변 공간 - 알고리즘이 수행되며 동적으로 할당되는 공간이 해당된다. 알고리즘과 밀접한 관련이 있다.
이를 함수로 나타내면 아래와 같다.
공간복잡도 = 고정 공간(상수) + 가변 공간
S(P) = c + Sp(n)
c는 상수이므로 공간 복잡도는 `가변 공간`이 좌지우지 하는 것을 알 수 있다.
- 이전 컴퓨터 사양이 좋지 않을 시절에는 중요히 여기는 지표였지만, 최근 컴퓨터 사양이 상향 평준화 됨에 따라 중요한 부분은 아니지만, IoT쪽이나 빅데이터 등을 다루는 문제에서는 가끔 다뤄질 때가 있다정도로만 참고하면 될 것 같다.
✔️시간 복잡도(Time complexity)는 뭔데 ?
프로그램이 실행되고 완료되기까지 사용하는 총 소요 시간을 의미한다.
엄밀히 따지자면, 시간복잡도는 컴파일 시간과 실행시간을 합친 의미이지만,
컴파일 시간은 공간복잡도의 고정 공간과 비슷하게 알고리즘에 영향을 받는 지표가 아니기 떄문에 코딩테스트 등을 풀이 할 때에는 고려되지 않는다.
- 코드가 실행되는
환경, 언어 등 여러 요인에 따라 같은 알고리즘 이라도 소요되는 실제 시간은 다르다. 따라서 시간 복잡도는 정확한 프로그램이 실행 시간을 초 단위로 표기하는 것이 아니라,명령문의 실행 빈도수에 따라 대략적으로 소요 시간을 나타내기 위해 사용된다. 따라서 같은 시간 복잡도를 갖는 코드를 C++ 와 Python 에서 각각 실행하면 실제 실행 시간은 다를 수 있다. - 시간 복잡도는 보통의 경우 점근 표기법 특히, 빅오 표기법(Big-O notation)을 사용한다.
✔️점근 표기법?
빅오 표기법 같은 알고리즘의 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 다섯가지 표기법이 있지만 빅오(Big-O) 를 주로 사용한다.
✔️빅오 표기법의 특징
시간 복잡도에 미미한 영향을 주는 것들은 배제하고 표기된다.
- 상수항을 무시 -> O(n+5) 복잡도를 가진다면 상수를 생략하여 O(n)으로 표기한다.
- 계수항을 무시 -> O(3n)의 복잡도를 가졌으면 계수를 생략해 O(n)으로 표기한다.
- 최고차항만 표기 -> O(
3n^3+2n^2+n+5)의 복잡도를 가졌으면 O(n^3)으로 표기한다.
✔️매서드 마다의 Big(o)
| method name | Big(o) |
|---|---|
| push() | O(1) |
| pop() | O(1) |
| shitft() | O(n) |
| unshift() | O(n) |
| splice() | O(n) |
| sort() | O(n log n) |
| concat() | O(n) |
| slice() | O(n) |
| indexOf() | O(n) |
| filter() | O(n) |
| reduce() | O(n) |
✔️많은 방법 중 굳이…? 왜? 빅오 표기법을?
빅오의 특징으로 눈으로 바로 파악 가능한 장점이 있다.
-
빅오 표기법은 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다
상한선 기준 -> 최악의 경우라고 생각하면 편하다. -
일상에서 예시를 들면 빅오 표기법은 최악의 경우를 가정하는것이라
이하라고 생각하자 -
추가로 빅 세타 표기법(하한과 상한 사이 평균정도의 의미)은
대략 x와 y사이쯤…? 정도로 이해하고 넘어가도록 하자.
✔️빅오 표기법의 종류?
✔️빅오 표기법 실행 속도
O(1)<O(log n)<O(n)<O(n log n)<O(N^2)<O(2^n)
✔️O(1) - 상수시간(Constant Time)
가장 빠르고 이상적인 속도
- 입력값에 상관없이 항상 일정한 시간이 걸리는 알고리즘이다.
- 배열이나 해시 테이블의 데이터에 접근할 때 O(1)의 시간 복잡도를 갖는다.
function getFitstElement(arr){
return arr[0];
}
✔️O(log N) - 로그시간(Logarithmic Time)
O(1)다음으로 빠른 시간 복잡도
- 문제를 해결하는데 필요한 단계들이 연산마다 줄어드는 알고리즘이다.
- 이진탐색, 힙 삽입/삭제 등이 O(log N)의 시간 복잡도를 갖는다.
function logCounter(n){
let loopCount = 0;
// [ i*=2 ] 부분으로 인해 연산이 조금씩 줄어든다.
for(let i=2; i<= n; i*=2){
loopCount++;
}
return loopCount;
}
// n이 16 일경우 총 반복횟수는 4번
// n이 100일 경우 대략 6이 된다.
logCounter(16)
✔️O(N) - 선형시간(Linear Time)
이를 표준으로 봤을때 이보다 느린 알고리즘을 비효율적이라 본다.
인풋의 증가 시 같은 비율로 증가 즉, n과 1:1의 관계를 가진 시간 복잡도
- 예로 한번의 반복을 수행하고 완료되는 선형 탐사가 O(N)의 시간 복잡도를 갖는다.
function countCharacters(str){
let count=0
for(let i=0; i<str.length; i++{
count++
}
return count
}
✔️O(N log N) - 선형 로그 시간
- 예로 힙 정렬이 O(N⋅logN)의 시간 복잡도를 갖는다.
✔️O(N^2) - 제곱시간(Quadratic Time)
2차 시간이라고도 하며, 인풋의 증가 시 n 의 제곱 비율로 증가
- 2중 반복을 돌게되는 알고리즘은 O(N^2)의 시간 복잡도를 갖는다.
function buildMatrix(arr){
let matrix = [];
for(let i=0; i<arr.length; i++){
matrix[i] = [];
for(let j=0; j<arr.length; i++){
matrix[i].push(arr[j]);
}
}
return matrix;
}
// n이 10일경우 100회의 연산이 실행된다.
✔️O(N^3) - 세 제곱시간
- 3중 반복을 돌게되는 알고리즘은 O(N^3)의 시간 복잡도를 갖는다.
✔️O(2^N) - 지수시간
- 예로 입력 원소로 만들 수 있는 부분집합의 모든 경우의 수를 도출할 떄 지수시간을 갖는다.
✔️O(N!) - 팩토리얼 시간(Factorial Time)
가장 느린연산이다.
- 예로 입력 원소로 만들 수 있는 순열의 모든 경우의 수를 도출할 때 팩토리얼 시간을 갖는다.
function factorial(n){
let num = n;
if(n === 0) return 1;
for(let i=0; i<n; i++){
num = n * factorial(n-1)
}
return num
}
//만약 n이 10이라면 약 360만번의 연산이 요구가 된다.
✔️정렬 알고리즘 비교
| Sorting Algorithms | 최악 | 최선 | 평균 | 최악 |
|---|---|---|---|---|
| Bubble Sort | O(1) | O(n) | O(n2) | O(n2) |
| Heapsort | O(1) | O(n log n) | O(n log n) | O(n log n) |
| Insertion Sort | O(1) | O(n) | O(n2) | O(n2) |
| Mergesort | O(n) | O(n log n) | O(n log n) | O(n log n) |
| Quicksort | O(log n) | O(n log n) | O(n log n) | O(n2) |
| Selection Sort | O(1) | O(n2) | O(n2) | O(n2) |
| Shell Sort | O(1) | O(n) | O(n log n2) | O(n log n2) |
| Smooth Sort | O(1) | O(n) | O(n log n) | O(n log n) |
✔️자료구조 비교
| Data Structures | Average Case | Worst Case | ||||
|---|---|---|---|---|---|---|
| Search | Insert | Delete | Search | Insert | Delete | |
| — | — | — | — | — | — | |
| Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
| Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
✔️참고자료
참고자료1 - 빅오표기법
참고자료2 - 빅오 표기법
참고자료3 - 빅오 표기법
참고자료4 - 알고리즘 비교
유튜브 - 빅오 표기법 이해
'CS > 알고리즘 & 자료구조' 카테고리의 다른 글
| 알고리즘 학습과 메모리 상관관계를 알아보자 (0) | 2023.10.19 |
|---|---|
| [자료 구조] 자바 컬렉션(Collection)에 대해 알아보자 - Java (7) | 2023.08.31 |
| 알고리즘을 처음 시작하며, 정렬된 배열을 병합해보자 (LeetCode - 88) (0) | 2023.08.24 |
