CS/Algorithm
빅오표기법 (big-O)
태나미
2022. 2. 24. 16:15
Big-O란 무엇인가?
- 알고리즘 성능을 수학적으로 표기해주는 표기법
- 시간과 공간 복잡도를 표현
- 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는게 목표, 상수와 같은 숫자들은 모두 1이 된다.
시간복잡도
- 시간복잡도란 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다.
- 알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데
- 수행시간에 해당하는 것이 시간 복잡도 Time Complexity
- 메모리 사용량에 해당하는 것이 공간 복잡도 Space Complexity
연산 횟수를 카운팅 할때 3가지 경우가 있다.
- 최선의 경우 Best Case
- 최악의 경우 Worst Case
- 평균적인 경우 Average Case
빅오표기법 예제
O(1)
- constant time
- 입력 데이터 크기에 상관없이 일정한 시간이 걸리는 알고리즘을 표현
O(N)
- linear time
- 입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘을 표현
O(N**2)
- quadratic time
- 입력 데이터가 커지면 커질수가 처리시간의 부담도 커지게 된다
O(N**3)
- polynomial / cubic time
- N squre와 비슷한 양상이지만, 데이터가 늘어남에 따라 가로세로 높이까지 늘어나기 때문에, 더 가파르게 올라갑니다.
O(2**n)
- exponential time
- Fibonacci와 관련, 데이터의 증가에 따라 시간이 현저하게 늘어납니다.
O(log n)
- 대표적 알고리즘 : binary search
- 한번 처리가 진행될때마다 검색해야하는 데이터의 양이 절반씩 떨어지는 알고리즘입니다
- 데이터가 증가해도 성능에 크게 차이나지 않습는다.
빅오 표기법 특징
상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시합니다.
정렬
시간복잡도 O(n²) 정렬 알고리즘
- 버블(bubble) 정렬
- 선택(Selection) 정렬
- 삽입(Insertion) 정렬
시간복잡도 O(nlogn) 정렬 알고리즘
- 병합(Merge) 정렬
- 힙(Heap) 정렬
- 퀵(Quick) 정렬
출처:
https://noahlogs.tistory.com/27