데이터 구조 및 알고리즘 - 소개

모든 개발자는 '최적의 코드'를 작성하기 위해 노력합니다. 노련한 개발자라면 '최적의 코드'라는 말에 익숙할 것입니다. 하지만 초보자를 위해 자세히 살펴보겠습니다. 최적의 코드는 더 빠르고 메모리를 적게 차지하며 읽기 쉬운 코드를 말합니다. 이것은 데이터 구조를 통해 이루어집니다. 즉, 컴퓨터에서 데이터를 정렬하거나 저장하기 위해 선택할 수 있는 다양한 방법입니다. 빠른 코드를 살펴보겠습니다.

시간 복잡도와 Big 'O' 표기법

시간 복잡도는 입력의 크기가 증가함에 따라 알고리즘의 실행 시간을 분석하는 방법이며 Big O Notation은 입력이 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가하는지에 대해 공식적으로 이야기하는 방법입니다.

We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases
let's look at the code below:

function addUpTo(n) {
  return n * (n + 1) / 2;
}

"n"의 크기에 관계없이 위의 코드에는 곱셈, 덧셈 및 나눗셈의 세 가지 연산이 항상 있습니다. 우리는 위의 코드가 O(1)의 Big O 표기법을 가지고 있다고 말합니다. 다른 예를 보자

function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

위의 예에서 루프가 통과하는 후속 작업 수는 인수 'n'의 값에 고정됩니다. 작업 수는 O(n)의 n-Big O 표기법의 배수로 제한됩니다. 예를 들어 다양한 형태를 취할 수 있는 관계의 추세에 더 관심이 있습니다.

f(n)은 선형일 수 있습니다(f(n) = n)

f(n)은 2차 방정식일 수 있습니다(f(n) = n )

f(n)은 상수일 수 있습니다(f(n) = 1)

f(n)은 완전히 다른 것일 수 있습니다!

공간 복잡성

빅오 표기법을 사용하여 공간 복잡성을 분석할 수도 있습니다. 즉, 알고리즘에서 코드를 실행하기 위해 할당해야 하는 추가 메모리 양, 즉 입력이 차지하는 공간을 포함하지 않고 알고리즘에 필요한 공간입니다.
참고해야 할 몇 가지 중요한 사항:

대부분의 프리미티브(부울, 숫자, 정의되지 않음, null)는 상수 공간입니다

.

문자열에는 O(n) 공백이 필요합니다(여기서 n은 문자열 길이임).

참조 유형은 일반적으로 O(n)입니다. 여기서 n은 길이(배열의 경우) 또는 키의 수(객체의 경우)입니다.

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

우리는 위의 코드가 O(1)의 Big O 표기법(일정한 복잡성)을 가지고 있음을 관찰할 수 있습니다. 즉, 입력 크기에 관계없이 동일한 양의 공간이 필요합니다.

이 블로그를 읽으면서 시간 및 공간 복잡성에 대한 통찰력을 얻었기를 바랍니다.