[JS] - Big-O

Big-O

• Big-O 는 알고리즘의 효율성을 나타내는 지표
• Big-O 를 이용하여 알고리즘의 성능을 판단
• 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다

시간 복잡도

• 알고리즘의 실행 속도 의미
• 얼마나 빨리 실행되는가?

공간 복잡도

• 알고리즘이 사용하는 메모리 사이즈
• 얼마나 많은 저장 공간이 필요한가?

Big-O 표기법

• 데이터 입력값(n)의 크기에 따라 영향을 받는다
• 영햘력이 큰 항 이외에 영향력이 없는 항들은 무시. 최악의 상황을 고려해서 표기, 입력값(n) 의 표기는 제한이 없다
• 상수항은 무시한다

O(1) : 스택의 push, pop, 해시 테이블의 Access
O(log₂n) : 이진 트리(BinarySearchTree)
O(n) : Traverse 트리, Traverse 링크드 리스트(for문)
O(nlog₂n) : 퀵, 병합, 힙 정렬
O(n²) : 삽입, 버블, 삽입 정렬

O(2n) -> O(n)

• 영향력이 없는 상수항 2 를 무시, O(n) 으로 표기

O(N² + 3N + 3) -> O(N²)

• 영향력 없는 상수항 무시, O(N²) 으로 표기

O(1)

• castant time
• 일정한 패턴을 말한다
• 입력값(n)의 크기와 상관없이 항상 일정한 시간 패턴을 보이는 것을 O(1) 이라고 표기
• 시간이 오래 걸리든 빨리 걸리든, 일정한 시간 패턴을 가진다면 O(1)

O(n)

• 일정하게 증가하는 패턴
• 입력값(n)의 크기에 따라 시간 패턴이 일정하게 늘어나는 것을 O(n) 이라고 표기
• 데이터 구조 길이가 길수록 시간이 오래걸린다? => O(n)

O(log₂n)

• 증가하는 속도가 줄어들면서 증가하는 패턴
• 이진 트리 탐색 (BinarySearchTree) 를 예로 들 수 있다
• 트리와 같은 구조로 자식이 2개 이하로만 존재하고 일정한 규칙으로 뻗어나가기 때문에 순서가 있는 데이터 구조로 정리되어 있다
• 첫 시행 후 반이 버려지고 또 탐색하고 반이 버려지는 것을 반복한다면 시간 패턴은 속도가 점점 줄어들면서 증가하는 패턴을 보이게 된다
• 이와 같은 패턴을 O(log₂n) 라고 표기

O(n²)

• 증가하는 속도가 점점 급격히 증가하는 패턴
• 버블 정렬을 예를 들 수 있다
• 이중 for 문을 사용하면서 정렬되지 않은 요소들을 하나하나 탐색해야 할 때 같은 패턴을 O(n²) 라고 한다