Time complexity (with JS) - Part 1

실제로 회사에서 근무했을당시 Nest js 를 활용한 백엔드 API 를 만드는 업무를 담당했었는데

 

그 당시에는 시간복잡도 라는 개념이 없엇기때문에  반복문 안에서 또 반복문을 사용하는 경우가 있었다

 

이런 경우에 연산속도가 엄청나게 늘어나기때문에 좀더 나은 방법을 찾아야 했었는데 그 때 찾아봤던 자료가 있어서 정리를 해보려한다

 

 

시간 복잡도, 그리고 Big - O 란?

 

시간복잡도는 알고리즘을 처리하는데 얼마의 시간이 걸리는지 말해준다, 이런 알고리즘의 시간복잡도는 주로 Big - O 로 표시를한다

 

Big - O 란 알고리즘의 성능을 수학적으로 표현해주는  표기법이다. 이를 통해 알고리즘의 시간과 공간 복잡도를 표현가능하다

 

Big - O 는 알고리즘을 실제처리하는 시간을 말해주는것이 아닙니다. 데이터나 사용자 증가에 따른 알고리즘의 성능을 예측하기위해 사용

 

O(1) : Constant Time

O(1)입니다. 입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘을 O(1)이라 말합니다

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

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

findO1(example);

example 이라는 배열 안에 5개의 element 가 있습니다 , example 안에 element 가 늘어나도 

 

findO1 함수는 배열의 첫번째 index 와 두번째 index element 만 찾고있습니다. 해당 과정은 한번만 이루어집니다

 

이런 알고리즘은 O(1)의 시간 복잡도를 가진다라고 표현

 

 

O(n) : Linear Time

O(n)입니다. O(n)은 입력 데이터의 크기에 비례해서 처리시간도 늘어나는 알고리즘을 표현할 때 사용

 

const people = ['jung', 'won', 'jay', 'louis', 'daniel'];

const findPerson = array => {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'daniel') {
      console.log("Found daniel");
    }
  }
};

findPerson(people);

people 배열의 길이는 5입니다 , 그렇기에 findPerson 안의 반복문은 총 5번만 동작합니다

 

하지만 people 배열의 길이가 늘어나면 늘어날수록 반복문이 동작하는 횟수도 비례해서 증가합니다

 

데이터가 증가함에따라 처리시간도 늘어납니다 , 데이터와 시간이 같은 비율로 증가하기때문에 시간복잡도 그래프는 직선으로 표시합니다

 

O(n^2) : Quadratic Time

입력 데이터의 크기의 제곱만큼 처리시간이 걸리는 알고리즘을 표현할 때 사용합니다.

const people = ['jung', 'won', 'jay', 'louis', 'daniel'];

const findPerson = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let k = 0; k < array.length; k++) {
      console.log(array[i], array[k]);
    }
  }
};

findPerson(people);

for 문안에 또 for 문을 활용해서 원하는 데이터를 구하는 함수입니다

 

people 배열의 크기가 늘어날수록 반복하는 횟수가 비례해서 늘어납니다 O(n)에 비해서 시간복잡도가 훨씬 늘어날겁니다

 

배열의 크기가 크지않다면 문제가없지만 배열의 크기가 늘어날수록 처리시간도 많이 늘어납니다

 

O(2^n)

피보나치수열을 표현한다면, O(2^n)을 표현할 수 있습니다.(제일 어려운 피보나치....너란녀석....)

function a(n){
  if(n <= 0) {
  	return 0;
  } else if(n === 1) {
  	return 1;
  }
  	return a(n-1) + a(n-2);
}

 

피보나치 수열을 구하는 코드를 재귀 함수를 통해 구현한다면 이렇게 표현할수있다고 합니다

 

함수를 호출할때마다 바로 전 숫자와 그 전 숫자를 알아야 숫자를 더하면서 앞으로 나올 숫자를 예상 가능합니다

 

매번 함수가 호출될때마다 두번씩 호출합니다 

 

n 의 제곱보다도 데이터의 증가에 따라 처리량이 현저하게 늘어나는 그래프를 볼수 있습니다

 

O(log n)

이진 탐색 등의 알고리즘을 표현할 때 사용합니다. 

let arr = [];

function log(k, s, e){
  for(let i = s; i <= e; i++){
    arr.push(i);
	let m = (s+e)/2;
    
    if(arr[m] === k){
      console.log(m) 
    } else if(arr[m]> k){
      return log(k, s, m-1);
    } else{
      return log(k, m+1,e)
    }
  }
}

굉장히 대표적인 알고리즘 이진 검색입니다

 

정렬된 배열에서 특정 값을 찾을때 이진검색을 이용하면 배열의 가운데 값과 키값을 비교해서 배열의 가운데 값이 

 

키값보다 작다면 키값보다 작은 값들은 신경 쓸 필요 없습니다

 

그러면 다시 없어진 배열 값을 제외한 elements 들 중에서도 중간값을 찾아서 키값과 비교합니다

 

한번 처리할때마다 검색해야하는 데이터의 양이 절반씩 사라지는 알고리즘은 O(log) 알고리즘이라고 합니다

 

이진검색을 사용하면 수많은 데이터가 있어도 성능은 크게 차이나지 않습니다

 

 

 

 

출처 : https://overcome-the-limits.tistory.com/18#%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84space-complexity

[자료구조] 시간복잡도 with JavaScript

글을 바탕으로 개인적으로 수정하였습니다