빅오 표기법(Big O Notation)

자바스크립트로 프로그래머스 입문 문제만 풀다가 

다음단계 문제로 넘어가면서 어려움을 많이 느꼈다.

유데미에 Javascript 알고리즘 & 자료구조 마스터 클래스를 진즉 결제했지만 이제는 봐야할 때인것 같아서

취업준비하며 알고리즘을 같이 공부하려고 한다

 

이 클래스의 1장은 빅오 표기법이고 알고리즘에 대해 설명하려면 필수적으로 훑고 가야하는 파트 인것 같아 정리를 해보려고 한다

 

---

# 빅오(Big O) 

입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식

함수 실행 시간이 변하는 관계를 의미, 입력의 크기와 실행시간의 관계

 

쉽게 말하면 알고리즘의 효율성을 표기해주는 표기법! 

 

알고리즘의 효율성은 데이터 개수 n개가 주어졌을 때 덧셈, 뺄셈, 곲셈, 나눗셈 같은 기본 연산의 횟수를 의미한다.

알고리즘의 시간복잡도와 공간복잡도를 나타내는데 주로 사용한다

→ 빅오 표기법은 보통 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리)효율성을 의미한다

 

 

# 빅오표기법의 특징

1. 상수항 무시

빅오 표기법은 데이터 입력값(N)이 충분히 크다고 가정하고 있고,

알고리즘의 효율성 또한 데이터 입력값(N)의 크기에 따라 영향 받기 때문에 

상수항 같은 사소한 부분은 무시한다

ex) O(2N)  →  O(N) 

2. 영향력 없는 항 무시

빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 떄문에

가장 영향력이 큰 항 이외에 영향력이 없는 항들은 무시한다

ex) O(N² + 2N + 1)   →  O(N²)

 

# 빅오 표기법 종류

시간복잡도 비교 : O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)

 

1. O(1) : 입력값(N)이 증가해도 실행시간은 동일한 알고리즘,

index로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도 - 기본 연산 수

ex) 스택에서 Push, Pop

 

2. O(log n) :연산이 한 번 실행될 때마다 데이터의 크기가 절반 감소하는 알고리즘

(log의 지수는 항상 2)

ex) 이진트리, 트리 형태 자료구조 탐색

 

3. O(n) : 입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘

ex) 1중 for 문

 

4. O(n log n) : 알고리즘의 실행 시간이 입력 크기와 입력 크기의 로그 곱에 비례

입력의 절반(또는 일부)으로 나눌 때마다 각 부분을 독립적으로 처리

ex) 병합정렬(merge sort), 힙 정렬(heap Sort),

      퀵 정렬(quick sort)은 평균적인 성능에서는 O(n log n) 최악의 시간복잡도는 O(n²)

 

5. O(n²) : 알고리즘의 실행 시간이 입력 크기의 제곱에 비례. 각 원소를 다른 모든 원소와 비교

ex) 이중 for문, 삽입 정렬(insert sort), 버블 정렬(bubble sort), 선택 정렬(selection sort)

 

6. O(2ⁿ) : 가장 느린 시간복잡도. 재귀적으로 수행하는 알고리즘에 해당

ex) 피보나치 수열