BigO Notation

intro

big o 표기법은 같은 문제를 해결하는 여러 방법, 즉 여러 알고리즘 중 어떤 것이 더 나은지 판단할 수 있는 기준이 된다. 어떤 알고리즘이 더 낫다고 이야기하는 것은 상황에 따라 다르지만, 빠른 속도와 적은 메모리 사용량이 보편적인 기준이다. 

 

+) 속도나 메모리 사용량 뿐만 아니라 코드의 가독성, 간편한 유지보수 가능성 등이 더 나은 코드를 판별하는 기준이 될 수 있다. 

time complexiry | how long to execute the function?

perfomance.now 이용하기

예를 들어 문자열을 input으로 받고, 그 문자열을 거꾸로 뒤집은 값을 반환하는 함수를 만든다고 해 보자. 이 함수를 구현해내는 방법은 아래의 두가지 외에도 많을 것이다. 둘 중 어떤 함수가 더 나은 함수일까? 우선 함수를 실행하는 데 걸리는 시간을 기준으로 답해보자. 

 

function reverse(input) {
  const lastIndex = input.length - 1
  let reveresedString = ''

  for (let index = lastIndex; index >= 0; index--) {
    reveresedString = reveresedString + input[index]
  }
  return reveresedString
}

function reverseWithArray(input) {
  const arrayOfInput = input.split('')
  return arrayOfInput.reverse().join('')
}

const time1 = performance.now()
reverseWithArray('hello hello hello hello hello')
const time2 = performance.now()
const duration = (time2 - time1) / 1000

 

위와 같이 코드를 작성하면 reverseWithArray 함수를 실행하는 데 걸린 시간을 확인할 수 있다. 마찬가지 방법으로 reverse 함수를 실행할 때의 걸리는 시간도 비교해 볼 수 있는데, reverseWithArray 함수를 실행할 때 더 짧은 시간이 걸리는 것을 확인할 수 있다. 그러나 함수를 실행할 때 마다 걸리는 시간을 수동적으로 재는 것은 번거로울 뿐만 아니라, 여러 가지 한계를 가지고 있다.

 

1. 어떤 기기에서 함수를 실행하느냐에 따라 그 값이 달라질 수 있다.
2. 같은 기기에서 여러번 performance를 측정할 때에도, 매번 그 값이 다르게 측정된다.
3. 시간 차이가 매우 작을 때에는 그 차이를 정확하게 측정하지 못할 수 있다.
4. 함수를 실행하는 데 얼마나 걸리는지 확인하기 위해서, 그 함수를 실행해야 한다. => 결과를 반환하는 데 1시간이 걸리는 함수가 있다고 생각해 보자.  

처리해야 할 연산의 개수 이용하기

환경에 따라 값이 달라지는 시간과는 달리, 컴퓨터가 처리해야 하는 연산의 갯수는 변하지 않는다. 따라서 각 함수가 처리해야 하는 연산의 갯수를 이용하면, 보다 객관적으로 성능을 비교할 수 있다. 아래 예제 addUpTo(n)은 1~n까지의 자연수의 덧셈을 반환한다. 예를 들어 addUpTo(3)은1 + 2 + 3의 결과를 반환한다. 

 

// 1. 3 개의 연산
function addUpTo(n) {
  return (n * (1 + n)) / 2 // 3 operaions(*, + , /)
}


// 2. 5n + 2 개의 연산
function addUpTo(n) {
  let total = 0 // 1 assignment
  for (let index = 1; index <= n; index++) {
    // 1 assignment, n comparisons, n additions & assignments
    total += total + index // n additions & assignments
  }
  return total
}

 

같은 결과를 반환하는 함수라고 해도, 첫 번째 경우는 n에 값에 관계 없이 항상 3개의 연산만 처리하는 반면, 두 번째 경우는 n의 값이 커짐에 따라 처리해야 하는 연산의 개수도 비례해서 커지는 것을 확인할 수 있다. 따라서 전자의 방법이 더 뛰어난 성능을 가지고 있다고 판단할 수 있다. 

what is BigO notation?

Big O notation is a mathematical notation that describes the ??? limiting behavior of a function when the argument tends towards a particular value or infinity. 

 

BigO 표기법은 앞서 설명한 연산의 갯수를 대략적으로(fuzzy counting) 나타내는 방법이다. 더 정교하게 이야기하자면, 함수의 input 값이 커질 때 알고리즘의 실행 시간은 어떻게 변화하는지를 다룰 수 있는 방법이다. 

 

big O graph

 

1. linear(선형) | f(n) = n => 알고리즘 f에서 인풋과 실행시간은 선형으로 비례한다. => O(n)이라고 표기한다. 
2. quadratic(2차) | f(n) = n^2 => 중첩 반복문, O(n^2)이라고 표기한다. 
3. constant(상수) | f(n) = 1, 2, ... => 알고리즘 f는 인풋 감에 관계없이 항상 동일한 실행 시간을 갖는다. => O(1)이라고 표기한다. 
4. 기타 등등

 

BigO 표기법은 함수의 인풋과 실행 시간 사이의 관계를 전반적인 추세로 나타내는 것이 목적이므로, n, 2n, 5n+2... 등등 상수에 관계 없이 모두 O(n)으로 표기한다. 같은 이유로 O(1), O(n^2)으로 표기한다. 다음은 몇몇 연산에 관한 시간 복잡도를 나타낸 것이다. 

 

1. 수학 연산(+, -, *, / ...)은 O(1)이다. 예를 들어 2 + 1이나, 2000 + 10293이나 값을 계산하는 데 걸리는 시간은 비슷하다. 
2. 변수 할당은 O(1)이다. 
3. index나 key를 이용해서 배열, 객체의 요소에 접근하는 것은 O(1)이다. 
4. 반복문은 O(n), 중첩 반복문은 O(n^2)이다. 

space complexiry | how much memory to allocate? 

지금까지는 함수를 실행하는데 얼마나 많은 시간이 걸리는 지(time complexity)에 관해 살펴보았다. space complexity는 함수를 실행하는 데 얼마나 많은 메모리 공간을 필요로 하는지를 설명한다. 이 때 함수의 input이 차지하는 메모리 공간은 고려하지 않으며, 함수(알고리즘)를 실행할 때 필요로 하는 메모리 공간 만을 복잡도 계산에 포함시킨다. 정확한 용어로는 axiliary space complexity라고 하는데, space complexity라고 하면 보통 이를 가리킨다. 공간 복잡도를 표현하는 데에도 BigO 표기법을 사용할 수 있다. 

 

1. 대부분의 원시 데이터(primitive type data)인 boolean, numbers, undefined, null)는 O(1)의 메모리 공간을 차지한다. => true나 false가 차지하는 메모리 크기, 1과 2000이 차지하는 메모리 크기는 같다. 
2. 반면 원시 데이터 중 문자열 데이터는 문자열의 length에 따라 O(n)의 공간을 차지한다. => 길이가 50인 문자열은 1인 문자열보다 50 배 많은 메모리 공간을 차지한다.  
3. 참조 타입 데이터(reference data)는 데이터의 length에 따라 O(n)의 공간을 차지한다. 

 

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

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

 

위의 add 함수는 total이라는 변수에 숫자 데이터를 재할당 하는 것이 전부이기 때문에, space complexity는 O(1)이 된다. 반면 double 함수는 newArray라는 변수에 배열을 저장하고, 그 배열의 아이템을 input의 길이만큼 추가하고 있기 때문에 space complexity는 O(n)이 된다. 

logarithm

로그 함수

로그와 지수의 관계

 

A logarithm is the power to which a number must be raised in order to get some other number. For example, the base ten logarithm of 100 is 2. 
=> base number인 b를 다른 숫자(b^x)로 만들기 위해 b의 지수가 되어야 하는 숫자(x)를 logarithm이라고 한다. 
=> 곱하기와 나누기의 관계 처럼, 로그함수는 지수함수의 역함수(reverse)이다. 로그는 지수 값을 나타내므로, base 숫자에 지수를 올리면(b^c) 원하는 숫자(a)를 만들어 낸다. 

 

로그는 추후에 다룰 sorting 알고리즘, recursion 등의 시간/공간 복잡도와 관련있다.