Big O

여러가지 코드를 일반적으로 서로 비교하고 성능을 평가하는 방법

시간복잡도,공간복잡도에 대한 높은 이해

하드웨어에 영향을 받지 않음

정확한걸 따지지 않고 전체적으로 따짐 (1000n이던 10n 이던 결국 n)

 

더 좋은 코드

• 빠른가?
• 메모리 사용이 적은가?
• 코드가 읽기 쉬운가?

 

예시 2가지

Big O : O(n)
function exBigO(n){
    let total=0;
    for (const i=0;i<=n;i++){
    	total+=i;
    }
  return total;
}

Big O : O(1)
function exTwoBigO(n){
    return n*(n+1)/2
}

exBigO 와 exTwoBigO를 비교해봤을 때 exTwoBigO가 더 빠르다.

n의 값이 100000,10000000 ... 이런식으로 입력되게 된다면 exBigO는 n에 따라서 반복문의 횟수가 결정되고

그에 따라서 i값도 증가되면서 total에 더해지게 되는 구조를 가지고 있다. (10n+2 이런식)

 

Big O 정의

 

알고리즘은 O(f(n))이라는 표현을 사용하고 여기서 f는 function이다.

 

f(n) = n 선형적구조 -> n의 값이 커질수록 실행시간이 늘어남 O(n) 

[#] O(n) 식이 2개이상 있어도 O(n)으로 표현한다.  O(2n) or O(1000n+50) -> O(n)

ex) for 문이 2개 따로 있을 때

 

f(n) = n^2  제곱 O(n²)

[#] O(n)식이 중첩되어 있을때 O(13n²) -> O(n²)

ex) for 문이 중첩되어 있을 때 

 

f(n) =1 상수 -> n이 커져도 아무영향을 받지 않음 O(1)

[#] O(40000) -> O(1)

...등등 다른 f(n)은 차차 소개하겠다.

 

 

 

공간복잡도

위에서 다뤘던 시간 복잡도와 달리 공간 복잡도는 간단하게 변수의 공간에 영향을 받는다고 생각하면된다.

아래 예시를 보면 let i=0는 O(1)의 공간복잡도를 가지고 let co=[]는 O(n)의 공간복잡도를 가진다.

 

원시형 O(1)
function hi(n){
	for(let i=0;i<=n;i++){
    	console.log(i)
    }
}


String,참조형 O(n)
function hi(n){
	let co=[];
    ~~
}

 

 

객체의 Big O

let person={
 name='sty',
 age='12',
 number='+10'
}

입력 || 제거 || 접근 - O(1)

 

-탐색-

Object.keys  - O(N)

key값이 늘어남에 따라 n 값도 증가하는 구조

Object.values - O(N)

value값이 늘어남에 따라 n 값도 증가하는 구조

Object.entries - O(N)

key와 value의 쌍이 늘어남에 따라 n값도 증가

hasOwnProperty - O(1)

True or False로 확인만 함

 

배열의 Big O

탐색 - O(N)

접근 - O(1)

삽입과 정렬은 어떤 메소드를 사용하느냐에 따라 달려있다 ( push, shift, slice 등등)

 

[참고]

https://careerkarma.com/blog/big-o-notation-time/

Big O Notation - Time Complexity