Big-O Notation

---

Big-O Notation : 알고리즘의 시간 복잡도나 공간 복잡도를 설명하는 데 사용되는 수학적 표기법

• 알고리즘의 효율성 및 비교하기 위해 사용함
• 알고리즘의 최악의 경우 성능을 나타냄
• 점근 표기법 (asymptotic notation) 의 하나

Big O 표기법 종류 §

1. $O(n)$
   • 알고리즘의 실행 시간이 입력 크기 $n$ 에 선형적(비례적)으로 증가함을 나타냄
   • ex)
     • $n$ 개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘¹을 적용
       • Best case : $O(n)$
         • 최댓값이 아닌 특정한 값을 찾을 경우에, 찾고자 하는 값이 배열의 첫 번째 위치에 있을 경우, Best case 는 $O(1)$ 이 된다.
       • Average case : $O(n)$
       • Worst case : $O(n)$
         • 마지막에 있거나 배열에 없을 경우
2. $O(\log n)$
   • 알고리즘의 실행 시간이 입력 크기 $n$ 의 로그에 비례하게 증가함을 나타냄 (로그 함수와 알고리즘 특징)
   • ex)
     • $n$ 개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘²을 적용
       • Best case : $O(1)$
         • 찾으려는 값이 배열의 중간에 위치할 경우
       • Average case : $O(\log n)$
       • Worst case : $O(\log n)$
         • 마지막에 있거나 배열에 없을 경우
3. $O(1)$
   • 알고리즘의 실행 시간이 입력 크기와 무관하게 일정함을 나타냄
4. $O(n^2)$
   • 알고리즘의 실행 시간이 입력 크기의 제곱에 비례하여 증가함을 나타냄
   • ex)
     • $n$ 개의 무작위로 나열된 수를 정렬시키기 위해 삽입 정렬³을 적용
       • Best case : $O(n)$
         • 이미 정렬된 배열을 다룰 경우
       • Average case : $O(n^2)$
       • Worst case : $O(n^2)$
         • 역순으로 정렬된 배열일 경우
5. $O(n\log n)$
   • 알고리즘의 실행 시간이 입력 크기 $n$ 과 입력 크기의 로그와의 곱에 비례함을 나타냄
   • 입력 패턴에 따라 정렬 속도에 차이가 있지만, 정렬 문제에 대해 $O(n\log n)$ 보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명됨
   • ex)
     • $n$ 개의 무작위로 나열된 수를 정렬시키기 위해 병합 정렬⁴을 적용

Footnotes §

1. 배열이나 리스트에서 특정 값이나 조건을 만족하는 요소를 하나씩 차례대로 확인하여 찾는 가장 기본적인 탐색 알고리즘 ↩

2. 정렬된 배열이나 리스트에서 특정 값이나 조건을 만족하는 요소를 탐색 범위를 반으로 줄여가며 수행하는 효율적인 탐색 알고리즘 ↩

3. 배열의 처음부터 끝까지 각 요소를 차례대로 방문하며, 현재 요소를 정렬된 부분 배열의 올바른 위치에 삽입함으로써 작동하는 간단하고 직관적인 알고리즘 ↩

4. 배열의 처음부터 끝까지 각 요소를 차례대로 방문하며, 현재 요소를 정렬된 부분 배열의 올바른 위치에 삽입함으로써 작동하는 간단하고 직관적인 알고리즘 ↩