본문 바로가기
  • soldonii's devlog
Javascript 공부/Data Structure + Algorithms(-)

자바스크립트에서 Big O(시간 복잡도)란?

by soldonii 2019. 8. 27.

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*https://soldonii.github.io에서 2019년 8월 19일(월)에 작성한 글을 티스토리로 옮겨온 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

1. 좋은 코드란?

어떤 코드가 좋은 코드일까?

 

좋은 코드의 조건은 크게 3가지이다.

① READABLE : 읽고 이해할 수 있는가
② EFFICIENCY : 메모리를 효율적으로 사용하는가
③ SCALABLE : input의 규모가 커져도 느려지지 않는가

Big O는 코드가 Scalable한 코드인지, 알고리즘을 수행할 때 시간이 얼마나 걸리는지를 측정할 때 사용하는 일종의 언어이다. 컴퓨터는 한정된 메모리 공간만을 가지기 때문에, 메모리 또한 효율적으로 관리가 필요한데, 이를 관리할 때 사용하는 개념이 공간복잡도이다.

 

2. Big O의 종류

Big O 차트

 

위 그래프는 input되는 element의 양이 많아질수록 작업량(operation)이 얼마나 늘어나는지를 나타내는 그래프이다. 오해하지 말아야 할 것은 Big O는 특정 작업이 수행되는데 시간이 얼마나 걸리는지, 그 시간을 측정하는 개념이 아니라 input의 증가에 따라서 runtime이 얼마나 빠르게 증가하는지를 측정하는 것이다.

 

몇가지 대표적인 Big O의 종류들을 사례와 함께 살펴보자.

 

# O(n) : Linear Time

const everyone = ['dory', 'bruce', 'marlin', 'nemo', 'gill', 'bloat', 'nigel', 'squirt', 'darla', 'hank'];

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

findNemo(everyone);

 

findNemo() 함수의 Big O를 계산해보자. everyone이라는 배열의 길이가 10이기 때문에, findNemo(everyone) 함수는 총 10번 동작한다. 즉 input되는 element의 개수와 작업의 수가 정비례 관계로 증가하는데, 이러한 경우를 Linear Time, O(n)이라고 말한다.

 

# O(1) : Constant Time

function compressFirstBox(boxes) {
  console.log(boxes[0]);
}

이 함수는 boxes 배열의 element가 얼마나 많은지와 관계없이 첫번째 element만 필요하므로 작업은 한 번만 이루어진다. 이러한 경우를 Constant Time, O(1)이라고 한다.

 

const boxes = [0,1,2,3,4,5,6];
function logFirstTwoBoxes(boxes) {
  console.log(boxes[0]); // O(1)
  console.log(boxes[1]); // O(1)
}

logFirstTwoBoxes(); // O(2)

이 경우 input이 아무리 많아져도 작업 횟수는 2회, 즉 O(2)이다. 하지만 O(2), O(3), O(100) 모두 input의 증가와는 별개이기 때문에 Constant Time이며, 모두 O(1)이라고 볼 수 있다.

 

# O(n^2)

// Log all pairs of array
const boxes = ['a','b','c','d','e'];

function logAllPairsOfArray(array) {
  for (let i = 0; i < array.length; i++) {
    for (let k = 0; k < array.length; k++) {
      console.log(array[i], array[j]);
    }
  }
}

logAllPairsOfArray(boxes);

O(n^2)의 경우 인터뷰에서 많이 마주칠 수 있는 문제이다. 속도가 빠르지 못하기 때문에 어떻게 성능을 개선시킬 수 있는지를 묻게 된다. loop 안에 nested loop을 만들 경우, Big O 계산에서 +가 아니라 *가 된다. 위의 경우 O(n * n), 즉 O(n^2)이며 이를 Quadratic Time이라고 부른다.

 

# O(n!)

O(n!)은 모든 element에 전부 nested loop이 가해진 구조이다. 이 코드는 가장 비효율적이고 가장 가파른 Big O이기 때문에 실무에서 볼 일은 거의 없으며, 내가 이런 코드를 쓴다면 아주아주 안 좋은거다.

 

참고로 Big O에는 소개된 것 말고도 몇 개 종류가 더 있다.

O(1) Constant- no loops
// O(log N) Logarithmic- usually searching algorithms have log n if they are sorted (Binary Search)
O(n) Linear- for loops, while loops through n items
// O(n log(n)) Log Liniear- usually sorting operations
O(n^2) Quadratic- every element in a collection needs to be compared to ever other element. Two nested loops
// O(2^n) Exponential- recursive algorithms that solves a problem of size N
// O(n!) Factorial- you are adding a loop for every element

Iterating through half a collection is still O(n)
Two separate collections: O(a * b)

 

주석처리한 것들은 data structure와 알고리즘을 배울 때 배우게 된다. 특정 상황에서만 사용되는 시간복잡도 개념이기 때문이다.

 

3. Big O 계산 규칙

Big O의 계산은 아래의 4가지 규칙을 따른다.

  • Rule 1 : Worst Case
  • Rule 2 : Remove Constants
  • Rule 3 : Different terms for inputs
  • Rule 4 : Drop Non Dominants

 

# Big O Rule 1 : Worst Case

말 그대로, Big O를 계산할 때는 항상 최악의 상황을 고려해야 한다는 내용이다.

 

const nemo = ['nemo'];
const everyone = ['dory', 'bruce', 'marlin', 'nemo', 'gill', 'bloat', 'nigel', 'squirt', 'darla', 'hank'];
const large = new Array(10000).fill('nemo');

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

findNemo(everyone);

 

이 코드의 경우, 니모를 찾기 위해 이 함수는 10번의 작업이 필요하다. everyone 배열의 element가 10개이기 때문이다. 사실 니모는 4번째에 위치해 있음에도 10번을 작업하고 있다.

 

const nemo = ['nemo'];
const everyone = ['dory', 'bruce', 'marlin', 'nemo', 'gill', 'bloat', 'nigel', 'squirt', 'darla', 'hank'];
const large = new Array(10000).fill('nemo');

findNemo = (array => {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'nemo') {
      console.log("Found NEMO");
      break; // 여기를 추가!
    }
  }
});

findNemo(everyone);

 

물론 간단하게 break; 를 추가하면 니모를 찾자마자 실행을 중지하므로 더 효율적이 코드가 되는 것은 맞다. 하지만 이는 코드의 효율성의 측면에서의 이야기이고, Big O를 계산할 때에는 사실 크게 의미는 없다. 왜냐하면 Worst Case를 고려해야 하기 때문이다.

이 경우 Worst Case는 길이가 10인 배열에서 니모가 맨 마지막 element인 경우이다. 이 경우 아무리 니모를 찾자마자 break를 건다고 해도, 니모가 맨 마지막에 있기 때문에 결국에는 10번을 반복실행할 수 밖에 없다.

 

이렇게 최악의 상황을 고려하면, input되는 element의 개수 증가에 따라서 작업 횟수도 정비례하게 증가하고 있기 때문에 위 경우는 O(n), Linear Time이 된다.

 

# Big O Rule 2 : Remove Constants

상수를 제거하라는 의미이다.

function printFirstItemThenFirstHalfThenSayHi100Times(items) {
  console.log(items[0]); // O(1)
  
  var middleIndex = Math.floor(items.length / 2);
  var index = 0;
  
  while (index < middleIndex) { // O(n/2)
    console.log(items[index]);
    index++;
  }
  
  for (var i = 0; i < 100; i++) { // O(100)
    console.log('hi');
  }
}

 

위 코드의 Big O를 계산하면 O(1 + n/2 + 100)이 되지만, 최악의 상황을 고려해서 만약 items 배열의 길이(n)가 1억개라면 어떻게 될까? 이 경우 1억에 1을 더하든, 100을 더하든, 1억을 2로 나누든 상황은 크게 달라지지 않을 것이다. 따라서 상수는 제거하고, 결국에 이 경우에도 Big O는 O(n), Linear Time이다.

 

function compressBoxesTwice(boxes) {
  boxes.forEach(function(boxes) { // O(n)
    console.log(boxes);
  });
  boxes.forEach(function(boxes) { // O(n)
    console.log(boxes);
  });
}

 

위도 마찬가지로 O(n)이 두번 반복되므로 O(2n)이지만, 상수는 버리기 때문에 O(n)이다. Big O 계산은 코드 계산 속도에 대한 이야기가 아니며, 그래프의 기울기가 아무리 가파르거나 느슨해도 그 선이 일직선이기만 하면 여전히 Linear Time, O(n)인 것이다.

 

# Big O Rule 3 : Different Terms for Inputs

function compressBoxesTwice(boxes, boxes2) {
  boxes.forEach(function(boxes) { // O(a)
    console.log(boxes);
  });
  boxes2.forEach(function(boxes2) { // O(b)
    console.log(boxes);
  });
}

 

이 코드의 경우 두 개의 input이 서로 다르다. 첫번째는 input이 boxes이고, 두번째는 input이 boxes2이기 때문에 각각의 크기에 따라서 작업 횟수가 달라진다. 인풋이 다를 경우에는 따로 계산을 해줘야 하기 때문에 이 경우 Big O는 O(a + b)이다.

 

# Big O Rule 4 : Drop Non Dominants

function printAllNumbersThenAllPairsSums(numbers) {
  console.log('these are the numbers');
  numbers.forEach(function(number) { // O(n)
    console.log(number);
  });
  
  console.log('and these are their sums');
  numbers.forEach(function(firstNumber) { 
    numbers.forEach(function(secondNumber) {
      console.log(firstNumber + secondNumber); // O(n^2)
    });
  });
}
printAllNumbersThenAllPairsSums([1,2,3,4,5]);

 

이 경우 O(n + n^2)인데, 상수를 제거하는 것과 같은 맥락에서 덜 중요한 것은 떨궈서 계산한다. numbers 배열의 길이가 커질수록 n + n^2에서 n의 중요도는 떨어질 수 밖에 없는 것이, n^2의 작업 횟수가 극적으로 증가하기 때문이다. 따라서 이도 결국엔 O(n^2), Quadratic Time이 된다.

 

4. 공간 복잡도(Space Complexity)

시간복잡도가 input되는 element의 증가에 따른 작업횟수의 증가를 보는 것이라면, 공간복잡도는 작업 수행 시 공간을 얼마나 추가로 사용하게 되는지를 보게된다.

 

# 공간복잡도에 영향을 미치는 요소

공간복잡도에 영향을 미치는 요소는 네가지이다. ① 변수, ② 자료구조(Data Structure), ③ 함수 호출(Function Call), ④ 할당(Allocation)가 그것이다.

function booo(n) {
  for (let i = 0; i < n.length; i++) {
    console.log('booo!');
  }
}

booo([1,2,3,4,5]);

 

공간복잡도를 계산할 때, input이 얼마나 큰지는 크게 중요하지 않다. 다만 특정 작업 내에서 메모리 공간을 얼마나 많이 사용하는지 보게 된다. 위 코드의 경우 함수 내에서 변수 i를 0이라고 선언한 것 외에는 공간복잡도에 영향을 미치는 다른 작업이 없기 때문에 이 경우 공간복잡도는 O(1)이다.

 

function arrayOfHiNTimes(n) {
  let hiArray = []; 
  for (let i = 0; i < n; i++) {
    hiArray[i]='hi';
  }
  return hiArray;
}

arrayOfHiNTimes(6); // O(n)

 

이 코드의 경우 공간복잡도는 O(n)이다. for문 내에서 변수 선언이 6번 반복적으로 실행되면서 공간을 6번 사용했기 때문이다.

 

 

이 모든 것들을 배우는 의미는 무엇일까?

자료구조형과 Big O

 

하나의 프로그램은 자료 구조(Data Structure)와 알고리즘(Algorithms) 조합의 결과물이다. 여기서 자료 구조는 데이터를 저장하는 방법에 대한 이야기이며, 알고리즘은 저장된 그 데이터를 이용하는 방법에 대한 이야기이다. 속도와 공간을 효율적으로 사용하는 것은 결국 어떤 문제를 해결하기 위해 올바른 자료구조형을 가져와서 효율적인 알고리즘으로 구현한다는 의미이기 때문에 이 모든 것들을 배우고 코딩에 적용해야 하는 것이다.

저작자표시

'Javascript 공부 > Data Structure + Algorithms(-)' 카테고리의 다른 글

자바스크립트의 자료구조 4 : 스택(Stack), 큐(Queue)  (0) 2019.10.08
자바스크립트의 자료구조 3 : 연결 리스트(Linked List)  (0) 2019.10.08
자바스크립트의 자료구조 2 : 해쉬 테이블(Hash Table)  (0) 2019.10.08
자바스크립트의 자료구조 1 : 배열(Array)  (0) 2019.09.26
자바스크립트의 자료구조  (0) 2019.08.28

관련글

댓글

티스토리툴바