<aside> <img src="/icons/list-indent_lightgray.svg" alt="/icons/list-indent_lightgray.svg" width="40px" />

Table Of Content

</aside>

자료 구조(data structure)는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.

<aside> 📢

알고리즘 분석이란?

알고리즘이 소모하는 자원을 분석하는 것 (자원 : 실행 시간, 메모리, 통신, 저장장치 등)

이 중에서도 일반적으로는 실행 속도에 초점을 두어 평가

• 시간복잡도(Time Complexity) : 속도의 관점에서 알고리즘의 수행시간 결과
• 공간복잡도(Space Complexity) : 메모리 사용량에 대한 결과 </aside>

복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

시간 복잡도

• 알고리즘이 입력 크기 n에 따라 얼마나 많은 연산을 수행하는지 함수로 표현하는 것
• 실행 시간은 실행환경에 따라 달라짐 (하드웨어, 언어, 운영체제 등)
  • 실행 시간 측정하는 대신 연산 횟수를 기준으로 분석
• 시간 복잡도를 표현하는 기법으로 점근적 표기법을 사용
  • 점근적 표기법 : 입력 크기가 매우 클 때 연산량 증가속도를 함수 형태로 나타냄
  • 점근적 표기법 중 가장 광범위하게 사용되는 것이 빅오 표기법(Big-O Notation)

빅오표기법

• $O(1)$ : 입력 크기와 관계없이 일정한 시간 → 상수 시간을 갖는 알고리즘

  function example(data) {
  	return data[0];
  }
  

• $O(n)$ : 입력 크기에 비례해 실행 시간 증가 (반복문)

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

• $O(n^2)$ : 입력 크기의 제곱에 비례 (2중 반복문)

  function example(data) {
  	for (let i = 0; i < data.length - 1; i++) {
  		for (let j = i + 1; j < data.length; j++) {
  			if (data[i] === data[j]) return false;
  		}
  	}
  	return true;
  }
  

• $O(log n)$ : 입력을 반씩 줄이며 탐색 (이진탐색)

빅오표기법

시간 복잡도란 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간이다.

주요 로직의 반복 횟수를 중점으로 측정되며, 보통 빅오 표기법으로 나타낸다.

예를 들어 ‘입력 크기 n’의 모든 입력에 대한 알고리즘에 필요한 시간이 $10n^2$ + n이라고 하면 다음과 같은 코드를 상상할 수 있다.

for (let i = 0; i < 10; i++) {
  for (let j = 0; j < n; j++) {
    for (let k = 0; k < n; k++) {
      if (true) console.log(k);
    }
  }
}

for (let i = 0; i < n; i++) {
  if (true) console.log(i);
}

빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것인데, 앞서 말한 코드의 시간 복잡도를 빅오 표기법으로 나타내면 O($n^2$)이 된다.