빅오(Big-O) 표기법

빅오(Big-O) 표기법

알고리즘 공부와 시간 복잡도를 판단할 때에 흔히 쓰는 단위?는 빅오 표기법입니다..
따라서 빅오 표기법에 대해 정리하려 합니다.

빅오 표기법

빅오 표기법은 알고리즘의 효율성(시간복잡도)를 표기해주는 표기법입니다.
데이터의 개수가 n개라 할 때, 해당 알고리즘의 시간 복잡도의 최댓값을 표기합니다.

예를 들어 n^2 + 2n + 3의 연산을 하는 알고리즘의 시간 복잡도를 빅오 표기법으로 따진다면 O(n^2)으로 상수와 영향력이 적은 항을 제외하고 나타낼 수 있습니다.

빅오표기법 시간복잡도 순서

빅오 표기법의 시간복잡도는 다음과 같은 순서로 나열할 수 있습니다.

O(2^n) > O(n^2) > O(n log n) > O(n) > O(log n) > O(1)

대표적인 빅오 표기법에 따른 이해

• O(2^n): n개가 있을 때 알고리즘의 시간 복잡도는 2^n입니다.
  • 예) 피보나치 수열
• O(n^2): n개가 있을 때 알고리즘의 시간 복잡도는 n*n 입니다.
  • 이중for문 또는 사입, 버블, 선택정렬
• O(n log n)
  • 퀵 정렬, 병합 정렬, 힙 정렬 등
• O(n): 단순한 for문과 같이 한번 반복하는 경우입니다.
• O(log n): 8 -> 4 -> 2 -> 1 과 같이 반복마다 탐색의 수가 줄어드는 경우입니다.
  • 이진트리
• O(1): 반복 없이 딱 한번의 연산을 말합니다.