03.알고리즘의 효율 분석(BigO,시간&공간 복잡도)

여기서 가르치는 내용은 이러하다.

어떤 알고리즘이 얼마나 잘 작동하는지 측정하는 작업

문제를 해결하는데 방법은 여러가지가 있다.

예를 들어 for문을 돌리는 방법도 있겠고 아니면 수학을 이용해서 하는 방법도 있겠다.

구현에만 초점을 두는 상황도 있겠지만 성능이 중요할 때가 분명히 있다.

어느게 좋은 성능을 내는지 알기 위해 공부를 시작한다.

시간 복잡도

알고리즘이 입력 크기에 따라 실행하는 데 걸리는 시간의 증가율을 나타내는 척도

코드로 보자.

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

function addUpToTwo(n) {
  return (n * (n + 1)) / 2;
}

지금 두 가지 코드를 가져왔는데 무엇이 더 오래 걸릴까?

무엇이 더 좋은 코드일까?

예를 들어 2번이 빠른 코드라고 한다면 그 이유는 무엇일까?

첫번째는 n에 관련 된 연산 5n , n과 관련 없는 연산 2개가 있다. (n에 값이 무엇인지에 따라 연산 갯수가 달라진다.)

그래서 5n+2다.

function addUpToTwo(n) {
  return (n * (n + 1)) / 2;
}

두번째 코드는 n과 관련없는 연산 (*,+,/) 총 3개다. (n에 값이 무엇인지 상관없이 연산 갯수는 동일하다.)

그래서 총 연산은 3이다.

근데 연산을 언제까지 다 새고 있는가?

너무 힘들고 복잡하다.

그래서 등장한게 Big O표기법과 시간복잡도다.

빅오 표기법

알고리즘의 시간복잡도나 공간복잡도를 입력 크기에 따라 가장 간단하게 나타낸 표현 방식이다.

정확한 연산 횟수를 세는 게 아니라, n이 커질 때 시간이 얼마나 증가하는지 추세를 보는 거다.

세부적인 연산횟수나 상수는 무시하고, 가장 중요한 성장패턴(입력크기 증가에 따른 연산 증가율)만 표현한다.

빅오 작성 규칙

변수배정도 상수다.
상수는 버린다.
산수는 상수라는 것.(덧셈,뺄셈,곱셈,나눗셈을 포함)
인덱스를 사용해서 배열 엘리멘트에 접근 하는 것
루프가 있다면 복잡도가 루프의 길이 곱하기 ex) O(n) x O(n) = O(n제곱)

왜 상수나 작은 값은 무시하는가?

입력값이 작을 땐 상수 값이 중요하지만 데이터가 커지면 무시해도 될 정도로 영향이 작아진다.

예를 들어

연산 횟수가 5n +2라면, 데이터가 아주 클땐 5n이 성능을 결정하고 +2는 무시해도 된다.
따라서 빅오표기법 "O(n)"이라고 표기한다.
앞에 상수도 제외하고 표기한다.

첫번째 함수는 5n+2고 상수나 곱셈 같은 것을 버리니까 O(n)이 되겠다.

두번째 함수는 3이고 상수만 있으니 O(1)이 되겠다.

O(1)	입력 크기에 관계없이 일정	배열 첫 요소 접근
O(log n)	입력 크기 증가 시 실행 시간 완만 증가	이진 탐색
O(n)	입력 크기에 비례	배열 전체 순회
O(n log n)	정렬 알고리즘	병합 정렬, 퀵 정렬
O(n²)	중첩 루프	버블 정렬, 선택 정렬
O(2ⁿ)	지수적으로 증가	피보나치 재귀
O(n!)	입력 크기 증가 시 극단적 증가	순열 생성

공간 복잡도

프로그램이 실행되는 동안 사용하는 메모리의 양을 측정

코드가 실행되면서 데이터와 변수,함수 호출,추가적인 자료구조 등 얼마나 많은 메모리를 먹냐를 따져보는 것

이또한 시간복잡도처럼 빅오 표기법을 사용한다.

알고리즘의 본질적인 공간 사용량만 측정을 위해 하는 가정

입력 데이터 자체가 차지하는 공간은 공간복잡도에 포함하지 않겠다

알고리즘이 실행되면서 사용하는 총 메모리 양을 측정한 것

여기에는 입력 데이터 자체가 차지하는 공간과 **알고리즘이 추가로 사용하는 메모리(변수, 스택, 힙 등)**를 모두 포함한다.

(다만 이 챕터에는 다루지 않고 연산에 따른 메모리양만 본다.)

별도의 언급이 없는 한 공간복잡도 라고 말하면 보조 공간 복잡도로 알고 있어라.

(둘이 별갠데 강의에선 편의를 위해 그렇게 한다고 함.

booleans,numbers,undefined,null에서 모두 불변 공간이다.

입력의 크기와는 상관없이, 숫자가 1,1000이든 모두 불변공간이라 여긴다.

문자열(string)은 다르다. 문자열은 O(n) 공간이 필요하다.

n이 문자열의 길이라면 50자가 있다면 1자보다 많은 공간이 필요할 것
reference 타입,배열,객체도 대부분 O(n)이라고 생각하면 된다.

이 예시를 보면 할당된 공간은 두개다. 그래서 2개가 메모리를 잡아먹는다.

그럼 공간복잡도는 n에 의해 변하는게 아니니까 O(1)인거지.

이건 공간복잡도가 n에 따라 변하니까 O(n)이 되겠다.

아래 코드의 공간복잡도는 무엇일까?

function logAtMost10(n) {
    for (var i = 1; i <= Math.min(n, 10); i++) {
        console.log(i);
    }
}

O(1)이다.

입력 크기 n과 무관하게 함수가 실행될 때 필요한 메모리 공간이 일정하다.

function onlyElementsAtEvenIndex(array) {
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            newArray[i / 2] = array[i];
        }
    }
    return newArray;
}

이건 O(n)이다.

함수가 입력 배열의 크기에 비례해서 새로운 배열을 추가적으로 생성하기 때문.

데일리코딩