빅오 표기법(Big O Notation)

빅오 표기법 필요성

코드가 작동하면 된다.~ 문제 해결만 하면 된다.~ 이렇게 생각할 수도 있지만…

엄청난 양의 데이터셋을 처리할 때, 해결 방법(알고리즘)에 따라 처리 속도가 1시간 이상 차이가 날수도 있다.

=> 성능이 중요하기 때문에 적합한 알고리즘을 사용해야 한다.

+ 코드의 성능을 얘기할 때 정확한 전문 용어를 사용하는 것이 중요하다.

 

더 나은 알고리즘은 무슨 뜻일까

더 빠른 것? 아니면 메모리를 더 적게 사용하는 것? 아니면 만들어지는 변수의 갯수? 아니면 함수 호출할 때마다 저장되는 데이터?

코드를 쉽게 읽을 수 있는 것? 짧은 것?

 

코드 실행 시간을 측정한다면?

문제1 : 기기(하드웨어)마다 다른 방식으로 시간을 기록하는데, 기기 사양에 따라 다를 수도 있다.

문제2 : 똑같은 기기가 같은 함수를 호출해도 다른 실행 시간을 기록할 수도 있다.

문제3 : 알고리즘은 정말 짧은 시간 안에 모든 것이 처리된다. => 속도 측정 정확도가 떨어진다.

 

=> 코드 실행 시간을 정확하게 측정할 수 있을까? 의미는 있겠지만 매순간 테스트를 해야할까?

===> 코드 실행 시간을 테스트 하지 않고도 코드를 비교하는 특정한 값이 필요하다!

======> 이럴 때 빅오 표기법이 유용하다.

 

시간을 측정하는 것은 문제가 있다. 그럼 어떻게 뭘 측정해야 할까?

코드 실행 시간을 측정하는 대신 컴퓨터가 처리해야 하는 연산 갯수를 셀 수 있다.

어떤 컴퓨터를 사용하든 연산 갯수는 변하지 않으니까.

 

정의

• 문제를 해결하는 방법이 여러 개가 있을 때 어떤 방법이 더 적합한지 서로를 비교하고 성능을 평가하는 방법
• 빅오 표기법은 코드를 분류하거나 비교할 수 있는 시스템이다.
• 알고리즘 성능 분석

 

시간 복잡도

• 입력이 커질수록 알고리즘이 얼마나 많은 실행 시간이 소요되는지
• 입력 데이터에 따라 알고리즘 실행 시간이 변하는 것을 설명한 공식적인 방식
• 입력 값과 함수 실행 시간이 변하는 관계 의미

 

빅오 표기법(시간 복잡도) 종류

n이라는 값이 입력되는 함수와 출력(입력과 실행 시간의 관계)

• 선형일 수 있다. n이 커질수록 실행 시간도 늘어난다.
  f(n) = n
• 2차일 수 있다. n이 커질수록 실행 시간이 n의 제곱일 수 있다. 그래프가 더 가파르다.
  f(n) = n²
• 상수 일 수 있다. n키 커져도 실행 시간에는 아무 영향도 받지 않기 떄문에 항상 상수
  f(n) = 1
• 아니면 패턴 없이 완전히 다르거나

 

빅오 표현식의 단순화하기

항상 맞지는 않지만, 대부분 맞는다.

상수도 필요 없고 끝에 작은 연산도 필요 없다.

• 산수는 실행 시간이 상수이다. 덧셈, 뺄셈, 곱셈, 나눗셈을 포함한다. n의 값과 상관없다.
  컴퓨터가 2+2 처리하는 시간과 10만+2 처리하는 시간 비슷하다.
• 변수 할당도 실행 시간이 상수이다. 컴퓨터가 변수에 값을 할당하는 데에 걸리는 시간은 비슷하다.
  x = 100과 x = 100000000 처리 시간이 비슷하다.
• 인덱스를 사용해서 배열 요소에 접근하는 것(key값을 이용해서 객체 요소에 접근하는 것)은 실행 시간이 상수이다.
  array[1]에 접근하는 것과 array[10000003]에 접근하는 것은 똑같은 시간이 걸린다.
• 루프가 있으면 복잡도는 루프의 길이 곱하기 루프 안에 있는 연산들이 된다.
  리스트에 있는 데이터를 루프로 처리할 때 0에서 n까지 간다면, n이 커질수록 루프 반복 횟수가 늘어난다.
  루프 안에서의 연산도 중요. 중첩 루프라면 실행시간이 n²으로 걸린다.

O(2n) ===> O(n)

O(500) ===> O(1)

O(13n²) ===> O(n²)

O(n + 10) ===> O(n)

O(1000n + 50) ===> O(n)

O(n² + 5n + 8) ===> O(n²)

 

• 모든 연산들을 다 세는 것은 힘들고, 사실은 정확한 갯수 조차 별로 중요하지 않다.
• 전체적인 추세를 중요하게 여긴다.

 

공간 복잡도

• 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는지
• 공간, 사용되는 메모리에 초점
• 입력되는 것을 무시하고 알고리즘 자체가 필요로 하는 공간을 의미한다.

 

공간 복잡도 이해하기

• boolean, number, undefined, null은 자바스크립트에서 모두 불변(constant) 공간이다.
  그렇기 때문에 입력 크기와 상관 없이 모두 constant
  boolean이 참이든 거짓이든 똑같은 공간 차지
• 문자열은 조금 다르다.
  문자열은 O(n)의 공간이 필요하다.
  만약 n이 문자열의 길이라면, 50자인 입력 값
  그 문자열은 길이가 1자인 문자열보다 50배 더 많은 공간을 차지하게 된다.
• 배열과 객체 같은 참조 타입들은 대부분 O(n)의 공간이 필요하다.
  n은 배열의 길이거나 객체의 키 갯수일 수 있다.
  배열1의 길이가 4이고, 배열2의 길이가 2이면 배열1이 배열2보다 2배 더 많은 공간을 차지한다.

 

빅오 표기법별 그래프

더 좋은 그래프(더 효율적이고 빠른 그래프)

O(1) > O(log n) > O(n) > O(nlog n) > O(n²)