목차
빅오 표기법이란
-
알고리즘의 시간과 공간복잡도를 나타내는데 사용하는 방식이다.
-
시간 복잡도는 알고리즘의 효율성을 의미하며, 공간복잡도는 알고리즘의 공간(메모리)의 효율성을 의미한다.
-
데이터 혹은 사용자의 입력값의 증가율에 따른 알고리즘의 성능을 예측 하는것이 목표 이므로 상수와 같이 변화가 없는 값의 시간복잡도는 1로 한다.
Ex) O(2n) => O(n) -
시간 복잡도를 나타낼때는 O(f(n))과 같이 나타낼 수 있다. Ex) O(n)
빅오 표기법의 종류
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n^2)
- O(2^n)
O(1)
- 입력 Data의 크기와 상관없이 일정한 시간이 걸리는 값을 의미한다.
- 예를들어 상수값, stack의 push, pop 등이 있다.
O(log n)
- 대표적으로 이진검색 알고리즘이 이에 해당한다.
- 이때 log의 지수는 2이다.
- 큰 입력값에도 크게 영향을 받지 않는 편이며, 매우 견고한 알고리즘이다.
O(n)
- 입력 Data의 크기에 비례해서 시간이 걸리는 알고리즘을 표현할때 사용한다.
- Data가 증가하면 시간도 같은 비율로 증가하므로 직선모양으로 그래프를 표현할 수 있다.
- 선형 시간 알고리즘 이라고 한다.
- 예를들어 1중 for문이 있으며, 정렬되지 않은 배열의 최댓값과 최솟값을 찾는 경우가 있다.
O(n log n)
- 대부분 효율이 좋은 알고리즘이 이에 해당 한다.
- 퀵정렬, 병합정렬, 힙정렬이 이에 해당한다.
- 입력값이 최선일 경우, 비교를 건너뛰어 O(n)이 될 수 있다.
O(n^2)
- 입력 Data의 크기가 커질수록 시간이 점점 오래 걸린다.
- 예를들어 2중 for문, 버블정렬, 선택정렬 등 비효율적인 알고리즘에 해당한다.
O(2^n)
- 대표적으로 피보나치 수열이 해당한다.
- 빅오 표기법 중 아주 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘이 이에 해당한다.
빅오표기법의 실행시간
- O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)
- 약 1억이 1초 정도 걸린다.
Ref
기본기가 탄탄한 개발자가 되자!