3 / 12 멘토링 체크포인트

시간복잡도

알고리즘의 실행 시간이 아닌 알고리즘을 수행하는데 연산이 몇 번 이루어지는지
T(n) 의 형태로 표기하지만 시간복잡도는 일반적으로 빅오표기법으로 나타냄
빅오표기법(O(n))
└연산 횟수가 다항식으로 표현될 경우 최고차항을 제외한 모든 항과 최고차항의 계수를 제외하고 표현
└최악의 경우를 나타낼 때 씀 (보통 최악의 경우를 가정하고 쓰므로 가장 많이 사용)
└최선은 빅오메가, 보통은 빅세타

const function (num) {
  let sum = 0 //대입 1회
  for (let i = 0; i < num; i++) { //반복문 n+1회
    sum += i //덧셈 n회
  }
  for (let i = 0; i < num; i++) { //반복문 n+1회
    sum += i //덧셈 n회
  }
  return sum //리턴 1회
}

T(n) = (1)+(n+1)+(n)+(n+1)+(n)+(1) = (4n+4) = O(n)

시간복잡도 표기

O(1) : 상수 시간

const function (num) {
  console.log(num)
}

입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)

O(logN) : 로그 시간

let arr = []
function log(k, s, e){ 
  for(let i = s; i <= e; i++){ 
    arr.push(i)
    let m = (s+e)/2
    if(arr[m] === k){
      console.log(m) 
    } 
    else if(arr[m]> k){ 
      return log(k, s, m-1
    } 
    else{
      return log(k, m+1,e) 
    } 
  }
}
출처:  [Plus Ultra]

한번 처리할 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘
대표적인 예가 이진 탐색

O(n) : 선형 시간

for (let i = 0; i < n; i++) {
  ...
}  

n번 반복문을 수행

O(n²) : 2차 시간

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    ...
  }
}    

이중 for문처럼 n이 커질때 n²에 비례해서 증가하는 경우

O(2ⁿ) : 지수 시간

const function (num) {
  if (num <= 1) {
    return num
  }
  return function(num-2) + function(num-1)
}  

대표적인 예시는 피보나치 수열
한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출

알고리즘의 성능 간 그래프

공간복잡도

작업 수행 시 공간을 얼마나 추가로 사용하게 되는지를 봄
알고리즘에 사용되는 메모리의 양 = 공간복잡도

1. 변수
2. 자료 구조
3. 함수 호출
4. 할당

공간복잡도에 영향을 미치는 네 가지 요소

O(n)

function sample(arr, n) {
  let s = 0 // 1
  for (let i = 0; i < n; i++) { // 2
    s += arr[i] // n
  }
  return s
} 

O(1)

function sample(n) {
  let val = 1; // 1
  for(let i=0; i<n; i++) { // 2
    val = val * i;
  }
  return val;
}