Big O Notation (Big O 표기법)

왜 사용하는가?

1. 코드의 효율성 판별
2. 수동적인 시간측정의 문제 해결

어떻게 사용하는가?

완벽한 시간을 구하는게 아님 ⇒ 연산의 갯수를 구하여 전체적인 추세를 파악하기 위함

 

1. 시간복잡도

 

종류:

1. O(1) : 값이변해도 시간이 변하지 않음 ⇒ 일직선
2. O(n) : n이 커질수록 시간도 n만큼 증가 ⇒ 리니어그래프
3. O(n**) : n이 커질수록 시간도는 n보다 더 증가 ⇒ 상승추세그래프

예시 1)

For루프

답: BigO = O(n)

 

단, n이 아무리 커도 5까지만 루프를 제한시키는 경우에는 O(1)이됨

 

예시 2)

단순 상수 계산

답: BigO = O(1)

 

예시 3)

2중For루프

답: BigO = O(n^2)

 

 

2. 공간복잡도

 

종류:

1. num,undefined,null,bool ⇒ O(1) (primitive value)
2. string ⇒ O(n)
3. Obj,Arr ⇒ O(n)

예시 1) number → O(1)

예시 2) Arr → O(n)

 

---

 

Obj의 시간복잡도

순서가 상관없기 때문에 기본적으로 빠르다.

search ⇒ O(N)

빼고 나머지 ⇒ O(1) (추가제거업데이트 등등)

다만 Object.key or value method ⇒ O(N) 배열을 리턴함

그러나 Object.hasOwnProperty ⇒ O(1) bool을 리턴함

 

 

Arr의 시간복잡도

순서가 있기 때문에 문제가 생길 수 있다.

입력과 삭제 = 앞→O(N) / 뒤→O(1)

search = O(N) ⇒ 배열 중 무엇을 하나하나 찾는다.

access = O(1) ⇒ 배열 중 무엇에 접근한다.