[코딩 테스트 준비] 빅오 표기법(Big O notation)

시간 제한이 있는 대회나 코딩 테스트를 준비하는 경우에는 주어진 시간 안에 문제를 효율적으로 해결하기 위해 암기가 필요한 부분이 있다. 시간 제한이 있는 환경에서 알고리즘 시간 복잡도를 고려하고 암기하는 데 도움이 되는 몇 가지 팁과 조건 확인 방법은 다음과 같다.

---

1. 문제 조건을 주의 깊게 읽고 이해합니다:
   • 문제의 시간 제한이 명시되어 있으며, 일반적으로 시간 제한은 초 단위로 주어집니다. 따라서 시간 제한이 1초인 경우, 알고리즘의 실행 시간이 그보다 훨씬 짧아야 합니다.
   • 입력의 최대 크기나 범위, 제한 사항 등도 주어지는데, 이를 통해 알고리즘의 최대 실행 시간을 예측할 수 있습니다.
2. 각 시간 복잡도에 대한 대표적인 예시를 암기합니다:
   • 주요 알고리즘의 시간 복잡도와 그에 대한 예시를 암기하는 것이 도움이 됩니다. 특히, O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n) 등의 시간 복잡도에 대해 익숙해지는 것이 중요합니다.
   • 암기해야 하는 빅오 표기법(Big O notation) 아래 참조
3. 문제를 해결할 때 가능한한 시간 복잡도가 낮은 알고리즘을 선택합니다:
   • 문제를 풀기 위해 가능한 한 시간 복잡도가 낮은 알고리즘을 선택해야 합니다. 주어진 시간 제한 내에 해결할 수 있는 가장 효율적인 알고리즘을 고려해야 합니다.
   • 예를 들어, 시간 복잡도가 O(n^2)인 알고리즘은 입력 크기가 큰 경우에는 사용하지 않는 것이 좋습니다.
4. 연습을 통해 익숙해집니다:
   • 다양한 종류의 알고리즘 문제를 풀며 알고리즘 시간 복잡도에 익숙해지는 것이 중요합니다. 많은 연습을 통해 각 시간 복잡도에 대한 직관을 키우는 것이 도움이 됩니다.
5. 문제를 해결한 후 코드 시간을 눈으로 측정하고 시간 복잡도를 분석합니다:
   • 문제를 해결한 후에는 해당 알고리즘의 시간 복잡도를 분석해보는 것이 좋습니다. 자신이 작성한 코드가 시간 제한 내에 실행될지 여부를 판단하기 위해서는 이러한 분석이 필요합니다.

---

 

빅오 표기법(Big O notation)은 알고리즘의 성능을 나타내는 표기법 중 하나로, 입력 크기에 따른 알고리즘의 실행 시간이나 공간 복잡도를 표현합니다. 빅오 표기법은 주어진 알고리즘이 얼마나 빠르게 실행되는지 또는 얼마나 많은 자원(메모리, 저장 공간 등)을 사용하는지를 분류합니다. 아래에 설명된 복잡도 종류들은 주로 알고리즘의 실행 시간에 초점을 맞춘 것입니다.

1. O(n) - 선형 복잡도:
   • 입력 크기에 비례하여 알고리즘의 실행 시간이 선형적으로 증가합니다.
   • 예를 들어, 배열의 각 요소를 한 번씩만 반복하는 경우가 이에 해당합니다. 배열에서 모든 요소를 한 번씩 순회하면서 각 요소를 출력하는 것은 배열의 크기에 비례하여 시간이 증가합니다.
2. O(n log n) - 선형 로그 복잡도:
   • 입력 크기의 로그값에 비례하여 알고리즘의 실행 시간이 증가합니다. 주로 효율적인 정렬 알고리즘들이 이에 해당합니다.
   • 예를 들어, 퀵소트(Quick Sort)와 합병 정렬(Merge Sort) 등이 이에 해당합니다. 퀵소트(Quick Sort)나 합병 정렬(Merge Sort)과 같은 정렬 알고리즘들은 배열을 반으로 나누어 정렬하고 다시 합치는 과정을 반복합니다. 이 과정은 로그 선형 복잡도로 실행됩니다.
3. O(n^2) - 2차 복잡도:
   • 입력 크기의 제곱에 비례하여 알고리즘의 실행 시간이 증가합니다. 주로 중첩 반복문이 이에 해당합니다.
   • 예를 들어, 이중 루프로 배열의 모든 요소를 비교하는 경우가 이에 해당합니다. 이중 반복문을 사용하여 배열의 모든 요소 쌍을 비교하는 정렬 알고리즘인 버블 정렬(Bubble Sort)이나 삽입 정렬(Insertion Sort)은 입력 크기의 제곱에 비례하여 실행됩니다.
4. O(2^n) - 지수 복잡도:
   • 입력 크기의 지수에 비례하여 알고리즘의 실행 시간이 증가합니다. 주로 완전 탐색(Exhaustive Search) 알고리즘 등이 이에 해당합니다.
   • 예를 들어, 모든 부분집합을 생성하는 경우가 이에 해당합니다. 모든 부분집합을 생성하거나 모든 순열을 생성하는 경우는 경우의 수가 지수적으로 증가하기 때문에 실행 시간이 지수 복잡도에 해당합니다.
5. O(1) - 상수 복잡도:
   • 입력 크기와 무관하게 알고리즘의 실행 시간이 일정합니다. 즉, 입력 크기에 상관없이 항상 일정한 실행 시간을 가집니다.
   • 예를 들어, 배열에서 첫 번째 요소를 반환하는 경우가 이에 해당합니다. 배열에서 첫 번째 요소를 반환하는 것은 입력 크기에 관계없이 항상 첫 번째 요소만 반환하므로 실행 시간이 일정합니다.
6. O(log n) - 로그 복잡도:
   • 입력 크기의 로그값에 비례하여 알고리즘의 실행 시간이 증가합니다. 주로 이진 탐색(Binary Search) 알고리즘이 이에 해당합니다.
   • 예를 들어, 크기가 n인 배열에서 특정 요소를 찾는 이진 탐색이 이에 해당합니다. 이진 탐색(Binary Search)은 정렬된 배열에서 특정 요소를 찾는 알고리즘으로, 탐색 범위를 반으로 나누어가면서 탐색합니다. 이 때마다 탐색 범위가 절반으로 줄어들기 때문에 입력 크기에 대해 로그 시간에 실행됩니다.
7. O(n!) - 팩토리얼 복잡도:
   • 입력 크기의 팩토리얼에 비례하여 알고리즘의 실행 시간이 증가합니다. 주로 완전 탐색 알고리즘이 이에 해당합니다.
   • 예를 들어, 순열을 생성하는 경우가 이에 해당합니다.

이러한 빅오 표기법은 알고리즘의 성능을 비교하고 선택하는 데 유용한 도구로 사용된다. 특히 알고리즘의 실행 시간이나 공간 복잡도를 예측하거나 평가할 때 사용된다.