알고리즘 시간복잡도와 Big-O

시작하기

어떤 알고리즘의 시간 복잡도(Time Complexity) / Big-O 를 논할 때
아래 그래프 정도만 숙지하고 있어도, 본인이 만든 코드의 시간 복잡도를 기반으로
대략적으로 계산 노드가 기하급수적으로 증가할 때 어떤 일이 벌어질 지 예측 가능합니다.

Big-O

Big-O 표기법의 특징

상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.

예를들어 O(3N) => O(N)와 같이 상수항은 무시하고 표기합니다.

영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

예를들어 O(N²+3N+2) => O(N²)와 같이 영향력이 지배적인 이외에 영향력이 없는 항들은 무시한다.

  • O(1) : 스택에서 Push, Pop
  • O(log n) : 이진트리
  • O(n) : for 문
  • O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
  • O(): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
  • O() : 피보나치 수열

big-O에는 다양한 실행 시간이 존재하지만 자주 사용 되는 것들은 다음과 같습니다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

N의 값 1 10 100
O(1) 1 1 1
O(log N) 0 2 5
O(N) 1 10 100
O(N log N) 0 20 461
O(N^2) 1 100 10000
O(2^N) 1 1024 1267650600228229401496703205376
O(N!) 1 3628800 화면에 표현할 수 없음!

Big-O: function ranking

O(1)

1
2
3
function sum(num1, num2) {
return num1 + num2;
};

이 기능은 O(1)입력과 관련하여 시간 (또는 “일정 시간”)으로 실행됩니다. 입력 배열은 1 개 항목 또는 1,000 개 항목 일 수 있지만이 기능은 여전히 ​​한 단계 만 필요합니다.

O(log n)

1
2
3
4
5
function log(n){
for(var i = 1; i <= n; i = i * 3){
console.log('i', i)
}
}

배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어듭니다.

O(n)

1
2
3
4
5
function forLoop(){
for(var i = 0; i < 10; i++){
console.log('i',i);
}
}

이 함수는 O(n)시간 (또는 “선형 시간”)으로 실행되며 여기서 n배열의 항목 수입니다. 배열에 10 개의 항목이 있으면 10 번 출력해야합니다. 항목이 1000 개이면 1000 번 출력해야합니다.

O(n²)

1
2
3
4
5
6
7
function forLoop(){
for(var i = 0; i < 10; i++){
for(var j = 0; j < 10; j++){
console.log('i, j',i, j);
}
}
}

여기에 두 개의 루프가 중첩됩니다. 배열에 n항목 이있는 경우 외부 루프가 반복 될 때마다 외부 루프 실행 n시간과 내부 루프 실행 n시간이 발생하여 총 2 회 출력됩니다. 따라서 이 함수는 O(n²)시간 (또는 “이차 시간”)으로 실행됩니다. 배열에 10 개의 항목이 있으면 100 번 출력해야합니다. 1000 개 항목이있는 경우 1000000 회 출력해야합니다.

O(2ⁿ)

1
2
3
4
function fibonacci(num){
if (num <= 1) return num;
return fibonacci(num - 1) + fibonacci(num - 2);
}

O(2ⁿ)함수의 예는 피보나치 수의 재귀 계산입니다. O(2ⁿ)은 입력 데이터 세트에 추가 될 때마다 성장이 두 배가되는 알고리즘을 나타냅니다. O(2ⁿ)함수의 성장 곡선은 기하 급수적으로 매우 얕게 시작하여 기상 적으로 상승합니다.

Fibonacci

Share