시간복잡도, 공간복잡도

학교에서 자료구조 수업을 들은 기억이 있다.

알고리즘에서 쓰이는 개념들을 어느정도 배웠었지만, 코딩테스트 준비는 심심할때마다 하는 것이 좋을 듯 하여 문서화해서 공부해보려 한다.

시간복잡도와 공간복잡도

컴퓨터는 보통 1초에 3~5억개 정도의 연산을 처리할 수 있다고 한다.

물론 우리가 High Level Language로 개발을 하면 복잡한 연산도 하나로 생각할 수 있겠지만,

컴파일 된 이후 어셈블리 언어에서는 instruction이 몇개가 나오냐는 다를 수 있기 때문에 대충 그렇다고 생각만 하면 좋을 것 같다.


const func = (arr, n) => {
  let count = 0;
  for (let i = 0; i < n; i++) {
    if (!(arr[i] % 5)) {
      count++;
    }
  }
  return count;
};

⇒ 5n + 3번의 연산이 필요하다.

📌

적당히 n번의 연산이 필요하다 라고 생각하면 된다.

입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

O(N): 5N + 3, 2N + 10logN, 10N O(N^2): N^2 + 2N + 4, 6N^2 + 20N + 10logN

입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

크기 N짜리 2차원 배열 ⇒ O(N^2)

배열이 필요 없음 ⇒ O(1)