[Algorithm] 알고리즘 복잡도

 

 

0. 알고리즘 복잡도

 

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

✔ 알고리즘 평가 지표

코테 시 메모리 사용량, 시간 복잡도를 중점으로 생각해야 함

✔ 시간 복잡도

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

• 3가지 점근적 표현법
  • Big-O(빅오): 최악의 상황을 고려 성능 측정 결과 표현
  • big-Θ(세타): 평균적인 경우 성능 측정 결과 표현
  • big-Ω(오메가): 최선의 상황일 때 성능 측정 결과 표현

 

✔ Big-O 표기법

1. O(1)
   상수일 때: 아무리 커도 상수이므로 1로 표현

function bigO(n) {
  let sum - 0; // 1회

  sum = n * 2; // 1회

  return sum; // 1회
}

 

2. O(N), O(N²)
   for문이 몇(n) 개로 중첩 되어있는지 -> 2중 for문일 때 n² 표기, 많이 느림을 표현

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

// n값이 얼마나 들어올지 모르기 때문에 n회라 함
  for (let i = 0; i < n; i++) {
    sum += arr[i];
  }
  return sum; // 1회
}

 

3. O(log N)
   나누는 대상이 있을 때 log로 표현

function big_o(n) {
  let sum = 0;

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

✔ Data Structure Operations, Array Sorting Algorithms

데이터 정렬 방식과 알고리즘 정렬 방식에도 시간복잡도가 사용된다.

http://www.bigocheatsheet.com