시간복잡도/공간복잡도

시간복잡도

어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간이 걸리는지’ 나타내는데 쓰인다.

시간복잡도는 빅오표기법으로 나타낸다. 

 

내가 정리한 빅오표기법

 

 

예시!

 

1. O(1) - n의 값과 상관없이 늘 일정한 시간이 걸리는 경우

const example = [1,2,3,4,5];

function findO1(example) {
  console.log(example[0]);
}

 

2. O(n) - n의 값에 비례하여 처리시간이 늘어나는 경우

const example = [1,2,3,4,5];

function findOn(n) {
  for (let i = 0; i < n.length; i++) {
    if (n[i] > 1) {
      console.log(n[i]);
    }
  }
}

 

3. O(n^2) - n의 제곱만큼 처리시간이 걸리는 경우

const example = [1,2,3,4,5];

function findOn2(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i],arr[j])
    }
  }
}

 

4. O(log n) - 이진탐색 알고리즘에 사용 (한번 처리할 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘)

 

 

 

시간복잡도 시간비교

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

 

 

공간복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양(메모리의 양)

 

예시!

 

1. O(1) 

function sum(arr){
  let total = 0;
  for(let i=0; i<arr.length; i++){
    total += arr[i];
  }
  return total;
}

몇 번의 반복문이 실행되어도 필요한 메모리는 total과 i 뿐이다. 그래서 O(1)의 공간 복잡도를 가진다. 

 

 

2. O(n)

function double(arr){
  let newArr = [];
  for(let i=0; i<arr.length; i++){
    newArr.push(2*arr[i]);
  }
  return newArr;
}

 

반복문의 횟수만큼 newArr는 늘어나게 된다. 그래서 O(n)의 공간 복잡도를 가진다.

 

 

자료구조에서의 시간복잡도