Big O Notation

Big O 표기법의 필요성

• Big O 표기법은 여러가지 코드를 비교하고 성능을 평가하는 일반적인 지표
• Big O 표기법을 통해 같은 동작을 하는 여러 코드들을 분류할 수 있음
• 코드는 원하는 동작대로 돌아가기만 하면 좋은 거 아닌가?
  • 어떻게 보면 맞는 말임
  • but, 면접, 코드 챌린지, 큰 데이터 셋을 다루는 기업에서는 동작도 동작이지만 성능 면에서도 우수해야 함
• Big O를 이해하면 어디서 문제가 나타나는 지 찾기 쉬울 수 있음
  • 에러 뿐만 아니라 코드를 실행시켰을 때 속도가 느린 것도 문제! → Big O를 이해하면 해결 가능(비효율적인 코드를 찾는 데 도움이 됨)

코드 시간을 재보자

• Example
  1 부터 특정한 값 N사이에 있는 모든 숫자들을 더하는 function을 작성해보자 (n = 6 이면 1 + 2 + 3 + 4 + 5 + 6 = 21)

• 가장 쉽게 접근할 수 있는 방법은 반복문을 사용해 1 부터 n까지 더해 리턴하는 방식

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

• 다른 방법은? 수학 공식을 활용하자
  $addUpto(n) = 1 + 2 + … + n$
  $addUpto(n) = 1 + 2 + … + n$
  위 두 식을 더하면?
  $2addUpto(n) = (n + 1) * n → addUpto(n) = n * (n+1) / 2$

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

• 위 두 코드 중 어떤 게 더 나을까?

  • 더 낫다의 기준? 기준은 상황에 따라 다름
    • but, 일반적으로 아래의 3가지를 중요하게 여김
    • 빠른 속도
    • 메모리 집약적인 코드
    • 읽기 쉬운 코드
  • 그 중에서도 속도와 메모리 사용량이 더 낫다의 척도를 판가름 함

• 코드 실행 속도 평가

  • 속도를 평가하는 가장 쉬운 방법은 내장 타이밍 함수(performance.now())를 이용하는 것

    function addUpto(n) {
    	let total = 0;
    	for(let i = 1; i <= n; i++){
    			total += i;
    	}
    	return total;
    }
    let t1 = performance.now();
    addUpto(1000000000);
    let t2 = performance.now();
    console.log(`경과시간: ${(t2 - t1) / 1000}초`);
    
    function addUptoByFormula(n) {
    	return n * (n + 1) / 2;
    }
    
    let t3 = performance.now();
    addUptoByFormula(1000000000);
    let t4 = performance.now();
    console.log(`경과시간: ${(t4 - t3) / 1000}초`);

  • 결과
    

  • 문제점

    • 측정 환경에 따라 시간이 달라질 수도 있다 → 신뢰성 ↓(but, 두번째 코드가 첫번째 코드보다 느리게 나올 일은 없음…)
    • 매우 빠른 알고리즘들은 정말 짧은 시간 안에 모든 게 처리됨 → 알고리즘들 간의 속도 비교가 어려움

• 시간을 측정하지 않고 코드의 속도를 비교할 수 있을까? → Big O 표기법!

  • 컴퓨터가 처리해야하는 연산 개수를 세면 됨
    ex) A 알고리즘은 처리해야하는 연산 개수가 5개, B 알고리즘은 처리해야하는 연산 개수가 7개

    • 각 알고리즘이 연산을 전부 처리하는데 걸리는 시간은 변동이 있을 수 있지만, 시간은 항상 연산의 개수에 달려있게 됨

  • 연산 개수 측정

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

    • 위 코드에서 연산 개수는 3개($*$ , $+$ , $/$) → n 값과는 관계 X, 반드시 3번 실행함

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

    • 해당 코드에서 연산자 $+$ 는 $n$ 에 따라 달라짐
      • $n$이 1이면 연산은 한 번 실행하겠지만 $n$이 1억이라면? 연산 횟수는 1억번 실행됨
      • i++ 연산도 n번 실행됨
      • 추가적으로 total = 0에도 1번의 할당 연산이 일어나고, i ≤ n n 번의 비교연산과, i = 1 에도 1번의 할당 연산이 일어남
    • 모든 연산을 세는 게 어려움…! → 연산 횟수가 상수가 X
    • 위 연산을 모두 합해 하나의 식으로 만들어본다면? $5n + 2$
    • but, 하나하나 구분하는 것이 중요하지는 X
    • 전체적인 추세(Big picture)를 보는 것이 중요!
    • 위 코드에서 바라봐야할 것은 $n$이 증가할 수록 연산 횟수도 증가한다는 것이 중요

Bio O Notation이란?

• 정의 $n$이 증가함에 따라 컴퓨터가 수행해야하는 작업의 수가 상수 f(n)보다 작은 경우 해당 알고리즘은 $O(f(n))$로 나타낼 수 있다
  • f(n)은 선형 함수($f(n) = n$), 이차 함수($f(n) = n^2$), 상수($f(n) = 1$) 등이 될 수 있음
• Big O notation은 대락적으로 숫자를 세는 것에 붙인 표현
• 입력 값이 증가함에 따라 알고리즘 실행 시간이 어떻게 변하는지 설명
• 즉, 입력 값의 크기와 실행시간의 관계를 의미
• Big O는 실행시간이 가질 수 있는 최대치에 관한 표기법
• 위 코드에서 addUpto(n) 함수는 $O(1)$의 복잡도를 가짐, addUptoFormula(n) 함수는 n이 커질 수록 실행시간이 선형적으로 증가하는 $O(n)$의 복잡도를 가짐
• ex)

  function countUpAndDown(n) {
  	for(let i = 0; i <= n i++) {
  		console.log(i);
  	}
  	for(let j = n - 1; i >= 0; j--) {
  		console.log(j);
  	}
  }

  • 위 코드는 for 루프 두 개가 존재 → O(n) + O(n) but, Big O notation에서는 크게 신경쓰지 않음 ⇒ $O(n)$

    function printAllPairs(n) {
    	for(var i = 0; i < n; i++) {
    		for(var j = 0; j < n; j++) {
    			console.log(i, j);
    		}
    	}
    }

  • 위 코드는 조금 다름(중첩 루프문)
  • $O(n)$의 복잡도를 가진 코드 안에 $O(n)$의 복잡도를 가진 코드가 있으므로 $O(n*n)$ → $O(n^2)$

Big O Notation을 단순화하자

• 상수는 신경쓰지 말자(입력 값 $n$이 충분히 크다고 가정, 알고리즘은 상수에 영향을 거의 받지 않기 때문) $O(2n) → O(n)$ $O(500) → O(1)$ $O(13n^2) → O(n^2)$자
  
• 영향력이 작은 연산도 무시하자(마찬가지로 n이 충분히 큰 값이라고 가정, 가장 영향력이 큰 항 외에 나머지는 알고리즘 복잡도에 영향을 크게 주지 X) $O(n + 10) → O(n)$ $O(1000n + 50) → O(n)$ $O(n^2 + 5n + 8) → O(n^2)$
  

Big O Notation 룰

1. 산술 연산과 변수 할당은 상수 시간의 복잡도를 가진다.
2. 인덱스를 사용해서 배열의 요소에 접근하는 것, 객체의 key 값을 이용해서 value에 접근하는 것도 상수 시간의 복잡도를 가진다.
3. 반복문의 복잡도는 반복문의 길이 x 반복문 안에 있는 연산이다.