Big- O Notation

BIG O Notation이 필요한 이유?

문제에대한 코딩을 할 때 여러가지 해결방법으로 풀 수 있다.

가령, join 메서드를 이용해서 문제를 해결한다던가 다른 메서드를 이용해서 문제를 해결하는 방법도 있다.

정답은 똑같이 도출되는데 그렇다면 어떤 문제해결방식(알고리즘)이 더 효율적일까?

효율성(성능)을 고려하는 것이 BIG-O Notation이라고 할 수 있다!!!

내가 개인 프로젝트를 하고 성능에 관계없는 코드를 짠다면 BIG-O Notation이 그렇게 중요하지 않을 수 있지만,

몇만줄을 실행하는 회사에서 한 줄의 코드 변경으로 인해 성능이 확 바뀐다면? 그게 BIG-O notation의 중요성이라면? 당연히! 필요하다.

좋은코드란?

주로 3가지를 본다.

• Speed(이 알고리즘이 얼마나 빠르게 실행되는가?)
• Memory Loss(이 알고리즘이 얼마나 메모리를 차지하는가?)
• Readable(이 알고리즘이 얼마나 쉽게 읽히는가?)

혼자 개발하면 가독성은 빼도 되지만 함께 개발하는 문화에서는 종종 실행 성능을 어느정도 포기하고 가독성을 높이는 경우도 많다.

Speed, Time Complexity (알고리즘 성능 확인할때 가장 중요한것 중 하나) 측정하는방법!

1. TimeStamp 사용하기

timeOne = performance.now()
// 이 곳에 성능 측정하고 싶은 코드 넣기
timeTwo = performance.now()

console.log(`이 알고리즘이 걸리는 시간은?: ${(timeTwo- timeOne) / 1000}`)

위의 방식을 자주 사용하지만 만약 특정 알고리즘이 엄청나게 시간소요(2시간, 4시간) 걸린다면?

1. BIG-O Notaion으로 짐작하기

• BIG-O Notaion이란 무엇인가? 특정 알고리즘(함수)의 Input값이 변함에 따라 성능(시간)의 변화를 대략적으로 측정하는것을 의미한다.

BIG O Notation의 종류

1. Big O could be linear (f(n) = n) → n operations
2. Big O could be quadratic(f(n) = n^2) → n^2 operations
3. BIg O could be constant (f(n) = 1) → 1 operation regardless of n size
4. Big O could be totally different

BIG O Notation Shorthands

1. Arithmetic operations ( + -)는 constant
2. 배열(Array)안에 요소들(elements) 접근할때 혹은 object의 key value 접근할때는 constant
3. 할당 (x = 20000, x=1)은 constant
4. loop function은 complexity N 하지만 안에 nested loop이 추가될때마다 n n ….

Space Complexity (공간 복잡도)

Shorthands

1. Most primitives(numbers, booleans, undefined, null) are constant space
2. Strings require O(n) space (where n is string length)
3. Reference types are generally O(n), where n is the length(array) or number of keys in objects

Logarithm - 왜 필요한가?

Big O 복잡도 계산을 할 때 O(1) O(n) 이런식으로 깔끔하게 복잡도가 계산되는 경우는 적다

대부분 O(logN) 이런식이라서 로그에 대해서 알아 두면 좋다.

Log란?

곱셈과 나눗셈이 항상 같이 나오듯이, 지수와 로그는 서로 붙어 있다

logn(8) = 3 → N^3 = 8 이 나오는 N의 값을 찾아라 정도다. 정답은 2