Algorithm

알고리즘이란 문제를 해결하는 방법
어떤 문제를 보다 효율적, 합리적으로 풀수록 좋은 알고리즘..

자료구조

사전적인 의미는 자료(Data)의 집합의 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.

자료구조와 알고리즘간의 관계

좋은 알고리즘을 만들기 위해 필요한것이 자료구조이다.

Algorithm의 선택기준

하나의 문제를 두고 다양한 알고리즘이 존재할 수 있다.
선택의 기준은 크게 실험적분석과 이론적분석이다.

실험적 분석과 한계

실험적 분석은 실제 실행시간(running time)을 측정하는 방법

/*
* Console.time()
* 타이머를 시작해 작업이 얼마나 걸리는지 추적가능
*/
  console.time("label"); // 측정 시작
  someFunc();
  console.timeEnd("label"); //측정 종료

실험적 분석방법은 알고리즘 외적 요인들로 인한 한계점이 있다.

• 하드웨어의 성능에 따른 영향
• 구현 언언에 따른 영향
• 현재 실행중인 다른 프로세스들의 영향

시간복잡도(time complexity)

• 실행시간은 실행환경에 따라 달라짐(하드웨어, 운영체제, 컴파일러 등)
• 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트
  - 어떠한 환경에서 실행하더라도 동일
• 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 => n에 관한 함수로
• 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐
  - 배열에서 원하는 값을 찾는 경우 찾는 값이 배열 어디에 위치하는지에 따라 달라진다.
• 최악의 경우 시간복잡도 (worst-case analysis)
  - 평균 시간복잡도가 구하기 더 어렵기 때문에 최악을 더 많이 사용
  • 데이터가 없는 경우, 모든 데이터를 다 비교하는 경우
• 평균 시간 복잡도 (average-case analysis)

이론적 분석

• O(1): 상수시간 내 처리 가능
• O(n): 선형시간 내 처리 가능
• O(n^2): 이차시간 내 처리 가능

n^3(다항함수)와 2^n(지수함수)는 굉장히 큰 차이가 있다!

빅오 표기법

빅오 표기법은 이론적 분석의 핵심이다.

• 최악의 경우 알고리즘의 복잡도(이론적 수행시간)을 나타낸다.
• O(1) 은 데이터 크기에 상관없이 일정한 복잡도를 갖는다.
• O(n) 은 데이터 크기에 정비례한 복잡도를 의미
• O(n^2) 은 데이터 크기의 제곱에 비례한 복잡도를 갖는다.

  일반적으로 빅오 표기법은 n의 가장 큰 지수만 고려한다.
  ex:) 총 연산결과가 3n^2 + 100n + 12345 === O(n^2)로 표현

상수 시간복잡도

입력으로 n개의 데이터가 저장될 배열 data가 주어지고, 그 중 n/2번째 데이터를 반환

const sample = (data, n) => {
  const k = n/2;
  return data[k];
}

n에 관계없이 상수 시간이 소요된다.
이 경우 알고리즘의 시간 복잡도는 O(1)

선형 시간복잡도

입력으로 n개의 데이터가 저장될 배열 data가 주어지고, 그 합을 구하여 반환

const sum = (data, n) => {
  let sum = 0;
  for (let i = 0; i < n; i++) {
    sum += data[i];
  }
  
  return sum;
}
/*
* 이 알고리즘에서 가장 자주 실행되는 문장이며, 실행 횟수는 항상 n번
* 가장 자주 실행되는 문장의 실행횟수가 n번이라면
* 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례하며,
*  모든 연산들의 실행횟수의 합도 역시 n에 선형적이다.
*/

선형 시간 복잡도를 가진다고 말하고 O(n)이라고 표기한다.
최악, 평균을 구분할 수 없다.

이차 시간복잡도

const sample = (n, data) => {
    for(let i = 0; i < n-1; i++){
        for(let j = i+1; j < n; j++){
          if (data[i] === data[j]){
            return false;
          }
        }
    return true;
   }
}

최악의 경우 배열에 저장된 모든 원소 쌍을 비교하므로 비교 연산의 횟수는 n(n-1)/2
최악의 경우 시간복잡도는 O(n^2)

Algorithm 문제 Tip

1. 알고리즘을 계산할 때 풀려는 문제의 수학 공식이 있는지 먼저 확인하는 것이 중요!!

let n = 100;
let s = 0;

// O(n)
for (const i = 1; i < n + 1; i++) {
  s += i;
}
console.log(s);

// O(1)
console.log(n*n(+1)/2);