Big O Notation (빅 오 표기법)

2021.08.26.

빅 오 표기법(Big O Notation) 은 알고리즘에서 가장 최선의 방법을 찾는 기준이 되는 방법이다.
코드에서 속도 저하나 크래시가 발생할 경우 비효율적인 부분을 찾아서 수정할 수 있는 기준이 된다.
알고리즘은 기본적으로 정답이 없지만, 빅 오 표기법을 통해 더 좋은 코드를 만들기 위한 기준점을 정할 수 있게 된 것이다.
빅 오 표기법에서 정확도는 중요하지 않으며 일반적인 경향에 대해 측정한다(linear, quadratic, constant)

ex) linear => O(N)

quadratic => O(N^2)

constant => O(1)

더 좋은 코드란?

더 빠른 코드, 더 적은 메모리를 사용하는 코드, 더 읽기 쉬운 코드 등이 기준이 될 수 있다.
알고리즘에서 더 좋은 코드를 정하는 기준은 보통 시간복잡도(Time Complexity)와 공간 복잡도(Space Complexity)가 있다.

cf) 로가리듬 복잡도(Logarithms Complexity)

로그로 복잡도를 계산하는 방식으로, 로가리듬에 의한 연산의 반복으로 복잡도를 측정한다.
로가리듬으로 구성된 알고리즘은 매우 효과적인 알고리즘이다.
회귀는 때때로 로가리듬적인 공간복잡도를 갖는다.

시간에 관한 문제(The Problem with Time)

알고리즘을 풀다보면 속도가 빠른 알고리즘을 일반적으로 좋은 알고리즘의 기준으로 삼는다. 그러나 우리가 프로그래밍을 작업하다보면 언제나 같은 환경에서 작업하는 것이 아니기 때문에 시간 측정에 문제가 생기게 된다. 가령 이런 문제를 생각해 볼 수 있다.

만약 실험 조건이 다른 컴퓨터라면 같은 알고리즘이라도 다른 시간이 나올 것이다. ⇒ 성능 차이 때문
그러나 실제로는 같은 컴퓨터로 실험하더라도 다른 시간이 나온다. ⇒ 항상 동일한 조건에서 실험할 수 없기 때문이다.
따라서 빠른 알고리즘의 속도 측정을 정의함에 있어서 시간의 정확도는 다소 떨어질 수 있다. 이를 보완하기 위해 나온 것이 Big O 표기법인 것이다.

Big O Notation이 필요한 이유

시간 효율성으로 알고리즘을 접근할 경우 알고리즘의 효율을 정확히 판단할 수 있는 근거가 부족하다. (다른 기기, 혹은 같은 기기에서도 시간 차이가 발생하고 측정 방법에 따라 오차가 발생할 수 있기 때문)
따라서, 시간을 정확히 측정하기보다는 연산의 개수를 세는 방식으로 알고리즘의 퍼포먼스를 측정할 수 있다!

예) 만약, 1부터 특정 숫자까지의 합을 구하는 함수를 만든다고 가정한다. 이때 특정 숫자는 n으로 표기한다.

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

// loop문에서는 loop문을 한번 반복할 때마다 1번 연산한 걸로 계산함

//2 =
function addUpTo(n) {
  return (n * (n + 1)) / 2
}
// multiplication / addition / division => 3 operation

console.log(addUpTo(6))

위의 첫번째 함수는 얼핏 보면 논리에 맞는것처럼 보인다. for문으로 total값에 계속 새로운 값을 더하면서 합을 반환하기 때문이다.
그러나 두번째 방식을 보면 결과는 같지만 계산하는 숫자가 훨씬 줄어든 것을 알 수 있다.
1번의 경우 숫자가 커짐에 따라 연산 숫자가 계속 늘어나는 반면, 2번의 경우 숫자가 바뀌더라도 연산의 숫자는 곱셈 + 덧셈 + 나눗셈 3번으로 고정되어 있음을 알 수 있다. 즉 2번 방식이 더 우수한 알고리즘이라 할 수 있다.

Big O 표기법의 특징

Big O 표기법은 모호한 카운팅 방법을 공식화하는 방법이라 할 수 있다.
Big O에서 연산자 수를 계산할 때는 사칙연산도 포함하지만 할당하는 것도 하나의 연산자로 계산한다. 즉, 알고리즘에서 연산이 n번을 사칙연산하던, n번을 할당을 하던, 인풋으로 들어오는 n의 크기에 비례하므로 n으로 계산한다.
알고리즘의 작동시간이 어떤 형태로 증가하는지를 공식적으로 표기하는 방법이다 (input이 증가할 때 마다)
**O(fn)**을 알고리즘의 연산 개수라고 하며, 알고리즘을 개선한다는 것은 N이 증가할때마다 **f(N)**을 어떻게 더 적게 증가시키는 지에 관한 것이라고 할 수 있다.
일반적으로 loop문을 돌리면 **O(N)**으로 표기할 수 있다. ⇒ n만큼 연산을 하기 때문

ex) 2중 loop문의 경우 **O(N^2)**이다. n만큼 n번 반복하기 때문
- 많은 연산을 하는 알고리즘일 수록 기울기가 더 가팔라지며, 비 효율적인 알고리즘임을 의미한다.

Big O 규칙

산술 방식(Arithmetic operation)은 일정하다(constant).
변수 할당(Variable Assignment)은 일정하다(constant).
인덱스로 배열 요소에 접근하거나, 키로 객체에 접근하는 것은 일정하다.(constant)

title: Space Complexity(공간 복잡도) date: 2021-08-26 18:08:47 category: Algorithm thumbnail: { thumbnailSrc } draft: false

시간 복잡도와는 달리 공간 복잡도는 얼마나 효율적으로 메모리를 할당해서 활용하는가에 중점을 둔다.
여기서 예비공간 복잡도(auxiliary space complexity)라는 개념이 나오는데, 알고리즘에서 말하는 공간복잡도는 일반적으로예비공간 복잡도를 기준으로 삼는다.

JS에서의 공간복잡도

대부분의 원시형은 일정한 공간을 사용한다.
문자열은 $O(N)$ 의 공간을 필요로 한다. (여기서 N은 문자열의 길이를 의미한다.)
참조 타입은 일반적으로 $O(N)$ 이며, N은 배열의 길이 혹은 객체의 키의 갯수를 의미한다.

공간복잡도 측정의 예시

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

// total, i가 선언되는 변수이므로 공간복잡도는 2이므로 상수인 O(1)이 된다!

function double(arr) {
  let newArr = []
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i])
  }
  return newArr
}
// 인풋데이터의 길이만큼 배열의 길이도 증가하므로 선형증가인 O(n)이 공간복잡도이다.