🧭 빅오 표기법

알고리즘에서의 시간 복잡도를 주로 빅오 표기법(Big-o)을 사용하여 나타냅니다.
시간 복잡도 : 시간이 얼마나 걸리냐를 나타내는 것

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

1. O(1)

입력 데이터의 양과 상관없이 실행 시간이 일정합니다.
ex. 해시 테이블의 조회 및 삽입

2. O(log n)

데이터 양이 많아져도 시간은 조금씩만 증가합니다.
시간에 비례하여 탐색 가능한 데이터양이 2의 n승이 됩니다.
이는 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형입니다.
ex. 이진 검색 ( 가운데에 위치한 값과 찾고자 하는 값 비교하면서 가운데 값을 바꿔가는 방법)

3. O(n)

데이터양과 시간이 정비례합니다.
ex. for 문을 통한 탐색, 리스트 순회 등

4. O(n log n)

데이터 양이 n만큼 많아지면 실행 시간은 n배 보다 조금 더 많아집니다.
큰 문제를 독립적인 작은 문제로 쪼개어, 독립적으로 해결 후 다시 하나로 모으는 경우에 나타납니다.
ex. 퀵 정렬, 병합 정렬 등

5. O(N^k)

데이터 양에 따라 걸리는 시간은 제곱에 비례합니다.(효율이 좋지 않음)
ex. n번 순회하는 반복문을 k번 중첩