01 Big O Notation ( in JavaScript )

Udemy | JavaScript Algorithms and Data Structures Masterclass

 

01 Big O Notation

 

● Big O Notation 이란 ??

 

좋은 코드, 더 나은 코드란 무엇일까? 란 질문을 던졌을 때 우리는 3가지 정도를 고려해 볼 수 있다.

 

01  기존 코드보다 처리 속도가 더 빠른가?

02  기존 코드보다 메모리를 덜 잡아먹는가?

03  기존 코드보다 로직이 더 직관적인가?

 

1번 조건을 평가하기 위해 쓰이는 도구가 바로 Big O Notation이다.

"시간 복잡도"라고 부르기도 한다. 알고리즘의 수행 시간을 분석할 때 이 시간 복잡도를 사용한다.

수행 시간은 실행 환경에 따라 다르게 측정되므로, 기본 연산의 실행 횟수로 수행 시간을 평가한다.

 

Big O 표기법은 '최악의 경우'를 나타낼 때 쓰인다.

진짜 이것보다 더 걸리진 않아  -->  마지노선의 느낌이랄까.

그치만 최악의 경우로 알고리즘을 평가해야 부수적인 효과들을 줄일 수 있지 않을까. 생각

 

 

● 속도 비교 

보통은 O( ) 이렇게 소괄호 안에 표기를 다르게 해서 표현한다.

우리는 앞으로 최대한 O(1)에 가깝게...^^ 코드를 리팩토링해야한다 ^___^

그래서 이게 무슨 말이냐 ?? 코드를 통해 알아보자

 

● O(1)

 

매개변수 n의 크기에 상관없이 표현식의 개수만큼만 수행될 때 O(1). 제일 빠름 호도도도

 

 

● O(n)

 

매개 변수 n만큼 표현식이 수행될 때 O(n).

 

 

n의 크기가 엄청나게 작든, 엄청나게 크든 n만큼 수행된다는 표기법이기 때문에 2n이든 10n+200이든 O(n)이다.

 

 

● O(n^2)

 

매개변수 n에 n을 곱한만큼 표현식이 수행될 때 ;;;  제일 별로인 아이 O(n^2).

알고리즘 풀면서 이중 for문 많이 썼었는데 자제좀 !! ( 그렇지만 쓰일 때가 또 있답니다 하핳 )

 

 

02  Space Complexity

 

● Space Complexity란??

 

2번 조건을 평가하기 위해 쓰이는 아이다. 

Spcae Complexity는 보조 공간과 입력 공간을 합친 포괄적인 개념으로, 알고리즘에서 사용하는 메모리 양을 나타낸다.

( 메모리 양을 계산한다고 해서 하드웨어가 알고리즘을 수행할 때 쓰는 메모리를 계산한다는 뜻은 절대 아니다 ! )

( 그저 알고리즘 안에서 평가되는 것뿐 ...! ) 

 

보통 원시 타입의 값들은 일정한 메모리를 차지한다.

그런데 객체 타입의 아이들.

배열이나 객체 안에 값이 무한히 들어갈 수 있는 아이들은 메모리 양을 가늠할 수가 없지 !!! 문제가 되지 !!! 

 

 

● O(1)

 

리턴되는 값이 원시 타입 하나다 ! O(1) !

 

 

● O(n)

 

리턴되는 값이 배열이다. 객체였어도 O(n)이었다. 왜냐하면 조건문에 의해 값이 계속 i만큼 추가되거든 !!