수학 기본 1 : 알고리즘 복잡도

알고리즘 복잡도(시간 복잡도)

- 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여 알고리즘의 수행시간을 평가하는 방법

- 3가지 점근적 표현법

• 빅오: 최악의 상황을 고려하여 성능 측정 결과 표현
• 세타: 평균적인 경우에서의 성능 측정 결과 표현
• 오메가: 최선의 상황일 때의 성능 측정 결과 표현

빅오 표기법

O(1)

function big_o(n) {
  let sum = 0; // 1회
  sum = n * 2; // 1회
  return sum;  // 1회
}

O(N)

function big_o(arr,n){
  let sum = 0; // 1회

  for(let i = 0; i < n; i++){
    sum += arr[i]; // n회
  }

  return sum; // 1회
}

O(N²)

function big_o(arr, n){
  let sum = 0; // 1회 

  for (let i = 0; i < n; i++){
    for (let j = 0; j < n; j++){
      sum += arr[i][j]; // n*n=n²
    }
  }

  return sum; // 1회
}

O(logN)

function big_o(arr, n){
  let sum = 0; // 1회 

  for (let i = 0; i < n; i *= 2){
    sum += 2; // n/2회
  }

  return sum; // 1회
}