빅오 표기법이란,
인수가 특정 값이나 무한대를 향하는 경향이 있을 때 함수의 제한 동작을 설명하는 수학적 표기법
작성한 코드가 얼마나 빠르고 효율적인지 판단하는 기준으로 시간 복잡도와 공간 복잡도를 사용한다.
시간 복잡도 : 실행 시간을 정량화한 것
공간 복잡도 : 실행하는 데 필요한 메모리 사용량을 정량화한 것
필요성
- 코드의 성능을 높일 수 있다.
- 어떤 알고리즘으로 접근할 것인지 판단하는데 용이하다.
- 에러를 제외한 코드 중 느리게 만드는 것을 찾는데 용이하다.
빅오 표기법은 입력 값에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도를 표현한다.
(이때 계수, 상수항은 무시하고 최고차항만으로 표현)
점근적 표기법 : 알고리즘의 복잡도를 나타날 때 계수, 상수항을 무시하고 표현하는 것
- 빅오 표기법 (Big-O Notation) : 최악의 경우
- 빅세타 표기법 (Big-θ Notation) : 평균의 경우
- 빅오메가 표기법 (Big-Ω Notation) : 최선의 경우
실행 속도
O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)
fast -> -> slow
빅오 복잡도 유형과 대표 예시
▶ O(1) : 지속적인 복잡도(상수) - stack에서 pop, push / 배열에서 특정 인덱스, 값 찾기
▶ O(log n) : 로그 복잡도 - 이진 탐색 / AVL 트리
▶ O(n) : 선형 복잡도 - 선형 탐색 / 1중 for문
▶ O(n log n) : 선형 로그 복잡도 - 퀵 / 병합 / 힙 정렬
▶ O(n²) : 2차 복잡도 - 버블 / 삽입 / 선택 정렬 / 2중 for문
▶ O(2^n) : 지수 복잡도 - 피보나치 수열 / 하노이탑 문제 / 부분 집합
▶ O(n!) : 계승 복잡도 - 외판원 문제(완전 탐색)
비교 정렬 알고리즘의 시간 복잡도
