[알고리즘 - 시간복잡도] 시간복잡도(Time Complexity)란? Bic-O표기법

시간복잡도란?(Time Complexity)

 

문제를 해결하는데 걸리는 시간을

시간복잡도라고 합니다.

 

걸리는 시간을 명확하게 알면 좋겠지만

같은 알고리즘이라도

서로 다른 성능의 컴퓨터 처리에 따라서

걸리는 시간 또한 각각 달라질 수 있습니다.

 

때문에,주로 점근적 분석법을 통해서시간복잡도를 나타냅니다.

 

점근적 분석법이란

입력되는 데이터의 크기에 따라 수행 시간과

공간이 얼마나 차지하는지 알아보는 탐색법입니다.

 

점근적 분석법에는 아래와 같이 3가지 표기법으로 나뉩니다.

 

최상의 경우 : 오메가 표기법 (Big-Omega(Ω) Notation)

평균의 경우 : 세타 표기법 (Theta(θ) Notation)

최악의 경우 : 빅오 표기법 (Big-O Notation)

 

평균의 경우는 기준이 모호하고,

최악의 경우를 고려하여 대비를 할 수 있어

주로 빅오 표기법을 사용하여 표기합니다.

 

이러한 빅오 표기법은

알고리즘의 효율성을 표기해주는 표기법인데,

알고리즘의 효율성이란 기본 연산의 횟수를 의미합니다.

또한 공간 복잡도는 알고리즘의 메모리 효율성을 의미합니다.

 

 

 

https://studiousguy.com/big-o-notation-definition-examples/

 

아래는 빅오 표기법의 예시입니다.

 

• O(1) : 입력 자료의 수(n)에 관계없이 일정한 실행 시간을 갖는 알고리즘(Constant Time)
  • 예시 : 배열에서 특정 인덱스 찾기, 해시 테이블 추가, 스택에서 Push, Pop
• O(log n) : 초반엔 빠르지만 후반부 갈수록 시간이 증가함
  • 예시 : 이진 탐색
• O(n) : 입력 자료의 크기가 N일 경우 N 번만큼의 수행 시간을 가진다.(linear)
  • 예시 : 연결 리스트 순회, 최댓값 찾기, for 문
• O(n log n) : 선형 로그형, 데이터의 수가 2배로 늘 때, 연산 횟수가 2배 조금 넘게 증가한다.
  • 예시 : 퀵 정렬, 병합 정렬, 힙 정렬 등
• O(n^2) : 주로 2중 for loop를 사용하여 조합 가능한 모든 쌍을 대상으로 하는 경우가 전형적(quadratic)
  • 예시 : 버블 정렬, 삽입 정렬, 거품 정렬, 선택 정렬
• O(n^3) : 3 차형(cubic)
• O(2^n) : 지수형 빅오, '지수적 증가'는 무서운 연산 횟수 증가를 야기한다.
  • 예시 :피보나치수열
• O(c^n) : 최악의 시간 복잡도 - exponential
  • 예시 : recursion
• O(n!) : 계승(factorial)

 

위와 같은 예시를 한번 자바스크립트로 구현해봤습니다.

 

const exampleArrLength = 100000;
const exampleArr = (function () {
const arr = [];
for (let i = 0; i < exampleArrLength; i++) {
arr.push(i);
}
return arr;
})();

// Case 1 : O(1)
// 어떤 입력 값에도 일정한 처리 속도
const caseOne = (arr) => {
return arr[0] === 0;
}
console.time('case-one');
caseOne(exampleArr)
console.timeEnd('case-one');

// Case 2 : O(log n)
// 이진 검색
const caseTwo = (key, arr, start, end) => {
if (start > end) return -1;
let middle = Math.floor((start + end) / 2);
if (arr[middle] === key) return middle;
else if (arr[middle] > key) return caseTwo(key, arr, start, middle - 1);
else return caseTwo(key, arr, middle + 1, end);
}

console.time('case-two');
caseTwo(23412, exampleArr, 0, exampleArr.length - 1)
console.timeEnd('case-two');

// Case 3 : O(n)
// 입력 값 수가 증가함에 따라 비례해서 처리 시간도 같이 증가
const caseThree = (arr) => {
for (let i = 0; i < arr.length; i++) {

}
}
console.time('case-three');
caseThree(exampleArr);
console.timeEnd('case-three');

// Case 4 : O(n log n)
// 퀵 정렬
const caseFour = (array) => {
if (array.length < 2) {
return array;
}
const pivot = [array[0]];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else if (array[i] > pivot) {
right.push(array[i]);
} else {
pivot.push(array[i]);
}
}
return caseFour(left).concat(pivot, caseFour(right));
}

console.time('case-four');
caseFour(exampleArr);
console.timeEnd('case-four');


// Case 5 : O(n^2)
// 2중 for 문, 입력 값 수가 증가함에 따라 제곱으로 증가
const caseFive = (arr) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
}
}
}
console.time('case-five');
caseFive(exampleArr)
console.timeEnd('case-five');

// Case 6 : O(n^3)
// 큐빅의 모양, 입력 값 수가 증가함에 따라 3제곱으로 증가
const caseSix = (arr) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
for (let k = 0; k < arr.length; k++) {
}
}
}
}
console.time('case-six');
caseSix(exampleArr)
console.timeEnd('case-six');

// Case 7 : O(2^n)
// 피보나치 수열
// const caseSeven = (num) => {
//     if (num < 2) return num;
//     return caseSeven(num - 1) + caseSeven(num - 2);
// }
// console.time('case-seven');
// caseSeven(100)
// console.timeEnd('case-seven');

// Case 8 : O(c^n)
// recursion


// Case 9 : O(n!)

 

임의 배열을 만들어 각각 케이스별로

실행하여 시간을 한번 체크해보았습니다.

 

간단하게 시간 복잡도에 대해 알아보았습니다.