BIG O with Javascript

 

하나의 결과물을 위해 많게는 수십, 수백가지의 경로가 있다. 

어떤 경로가, 어떤 코드가 좋은 코드일지 어떻게 알 수 있을까.

 

얼마나 빠른지, 메모리는 얼마나 차지하는지, 가독성이 좋은지. 대표적으로 이 세가지가 있다.

 

빅오는 코드의 효율, 성능을 비교할 수 있게 하는 기준이다.

빅오를 통해 각 코드의 시간복잡성과 공간복잡성을 비교할 수 있다.

 

 

1. 시간복잡도

 

실제로 이 코드를 동작했을 때 얼마의 시간이 걸리는 지. 로 코드의 성능을 평가할 수 도 있다. 

하지만 변수들이 너무 많아 정확성 측면에서 부족하다.

예컨데 성능이 다른 기기에서 실행을 한다거나, 같은 기기라도 기기가 어떤 상태에서 코드를 실행했는지도 영향을 미친다.

 

그래서 빅오를 통해 시간복잡성을 측정한다.

빅오는 걸리는 시간이 아닌, 컴퓨터가 처리해야 하는 연산의 개수를 세는 것.

 

1부터 n 까지의 숫자의 합을 세는 함수가 두개 있다.

 

1)

n * (n+1) / 2

2)

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

 

1) 함수는 연산이 3개 있는 반면,

2) 함수는 total = 0, i = 0, (배정도 연산이다) , i++, total = total+1, 그리고 n값에 따라 값이 증가하게 된다.

 

n값에 따라 값이 증가한다는 개념이 중요하다. 

 

1)의 경우 n값의 증가에 상관없이 연산의 수가 상수 3으로 고정되어 있다.

2)의 경우 n값이 무한대로 크다면 연산도 마찬가지로 무한대로 커지게 된다.

 

큰 그림을 보는 것이 중요하다.

 

빅오그래프

입력된 크기에 대한 실행시간의 관계를 나타내는 그래프이다.

 

- 연산이 상수일 경우 빅오가 O(1) 이라고 표현할 수 있다. 

- 산수 (덧셈, 뺄셈, 곱셈, 나눗셈), 변수 배정, 인덱스를 사용해서 배열 요소에 접근, key값을 통해 오브젝트 요소에 접근하는 것도 실행시간이 상수이다. 

- 순회하는 경우 연산의 개수는 5n+2 이런식으로 나오고는 하는데, 아주 큰 수를 기준으로 봤을 때 n앞이나 뒤에 붙은 숫자들은 상관이 없다. O(n) 으로 표현할 수 있다.

- 함수가 중첩되어 있을 경우 중첩된 수 만큼 제곱이된다. ex) 2중 for문 - O(n^2)

 

예시

const logAtLeast5 = (n) {
	for (let i = 1; i<=Math.max(5,n) ; i++) {
		console.log(i);
	}}

->O(n)

 

const logAtLeast5 = (n) {
	for (let i = 1; i<=(Math.min(5, n); i++) {
		console.log(i);
	}}

->O(1) : n값이 늘어나도 연산의 개수에 영향을 미치지 않는다.

 

n이 커지면 커질수록 연산도 커지는지, n이 커져도 연산은 그대로인지.

 

1. O(1) : 스택의 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2ⁿ) : 피보나치 수열

 

2. 공간복잡도

얼마나 많은 메모리를 차지 하는지. 최근 대용량 시스템이 보편화 되면서 시간복잡도 보다는 중요성이 떨어졌다.

 

기본 규칙. 

boolean, 숫자, undefined, null은 모두 불변 공간이다. 

입력의 크기와 상관없이 모두 불변공간이라 여긴다. ( 상수 - O(1) ) 

 

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

 

reference타입, 배열 객체도 같다. 대부분 O(n) 공간이 필요하다. n은 배열의 개수, 객체 키의 개수. 

 

result = 0;
for (let i = 0; i <=100; i++) {
	result +=i
    }

반복문이 n번 반복해도 변수는 result, i 이 두가지 이다. 공간복잡도는 O(1)

 

 

 

 

결론적으로 중요한 것은 몇번 반복하는 지와 같은 정확한 숫자가 아니라 전체적인 추세라는 것. 

빅오로 측정되는 알고리즘의 시간과 공간 복잡도는 하드웨어의 영향을 받지 않는다는 것.

 

 

3. with Javascript

 

 

1) Object

객체구조 : 순서가 필요 없고, 효율적으로 값에 접근하기 위해 사용

const object = {
	name : “lala”,
	age : “11”,
	}

값을 추가하는 것 - O(1)

값을 삭제하는 것 - O(1)

값에 접근하는 것 - O(1)

값을 찾는 것 - O(n)

 

 

+ Object Methods

Object.keys - O(n)

Object.values - O(n)

Object.entries - O(n)

hasOwnProperty - O(1) --> object.hasOwnProperty("name") // true or false : 값에 접근하는 개념이기 때문.

 

 

 

2) Array

정렬이 되어 있는 구조이다. 연산을 하는 시간이 더 걸릴 수 있다. 특히 입력과 제거.

const array = ['lala', 11]

값을 추가하는 것 - 상황에 따라 다름. 마지막에 push 한다면 O(1), 처음에 unshift한다면 O(n)이다.

왜냐하면 다른 값들의 인덱스가 모두 변경되기 때문에. 

 

값을 삭제하는 것 - 위와 마찬가지. 

값에 인덱스로 접근하는 것 - O(1)

값을 찾는 것 - O(n)

 

+array methods