1. 알고리즘 빅오표기법이란?
- 알고리즘의 시간 복잡도를 나타내는 표기법으로, 입력 크기가 무한대로 커질 때 알고리즘의 성능이 어떻게 변하는지를 분석(점근적분석)하는 방법입니다.
- 빅오표기법은 알고리즘의 최악의 경우 실행 시간을 기준으로 표기합니다.
- 대표적으로 O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!) 등이 있습니다.
2. 빅오표기법이 중요한 이유
- 빅오표기법을 이용하여 알고리즘의 시간 복잡도를 분석하면, 입력의 크기가 커질 때 알고리즘의 성능이 어떻게 변하는지 빠르게 예측할 수 있습니다.
- 예를 들어, 두 개의 알고리즘이 있을 때 각각의 알고리즘은 다음과 같은 시간 복잡도를 가진다고 가정해봅시다.
- 알고리즘 A: O(n)
- 알고리즘 B: O(n²)
- 만약 입력 크기 n이 작을 때는 두 알고리즘의 실행 속도가 큰 차이가 나지 않을 수 있습니다. 그러나 입력 크기 n이 커지면 알고리즘의 실행 속도는 급격하게 차이가 나게 됩니다.
- 예를 들어, 입력 크기 n이 100,000일 때, 알고리즘 A는 100,000번의 연산을 수행하고, 알고리즘 B는 10,000,000,000번의 연산을 수행하게 됩니다. 이는 알고리즘 B가 알고리즘 A에 비해 100,000배 느리다는 것을 의미합니다.
- 따라서 빅오표기법을 이용하여 알고리즘의 시간 복잡도를 분석하고, 입력 크기가 커질 때 알고리즘의 실행 속도가 어떻게 변하는지 예측할 수 있어야 합니다.
- 이를 통해 불필요한 계산을 줄이고, 더 효율적인 알고리즘을 선택함으로써 프로그램의 실행 속도를 향상시킬 수 있습니다.
- 빅오표기법은 서비스 관점에서도 매우 중요합니다. 서비스는 종종 대용량의 데이터를 다루며, 이를 효율적으로 처리하기 위해서는 빠른 실행 속도를 보장해야 합니다. 따라서 서비스에서 사용되는 알고리즘의 최악의 경우의 시간 복잡도는 매우 중요한 요소 중 하나입니다.
3. 빅오표기법 쉽게 계산하는 방법
- 알고리즘의 시간 복잡도를 계산할 때, 가장 영향력이 큰 항목(최고차 항의 차수)만 고려하면 됩니다.
- 상수항과 낮은 차수의 항목은 무시하고, 가장 큰 차수의 항목만을 남겨 O 표기법으로 나타냅니다.
- 예를 들어 알고리즘 시간복잡도가 2n + 1이면, 빅오표기법으로는 최고차 항의 차수인 O(n)이 됩니다.
4. 빅오표기법 예시 코드
- 예를 들어, 다음과 같은 코드의 시간 복잡도는 O(n)입니다.
for i in range(n):
print(i)
- 위 코드는 for 루프를 사용하여 n번 반복하면서 i를 출력하는 코드입니다. 이 경우 입력 크기는 n이며, 반복문을 실행할 때마다 한 번씩 i를 출력하므로, 총 n번의 연산이 수행됩니다.
- 따라서 이 코드의 시간 복잡도는 O(n)입니다. 즉, 입력 크기 n이 증가할 때, 실행 시간도 n에 비례하여 증가합니다.
- 다음은 O(n²) 시간 복잡도를 가지는 이중 반복문을 사용한 코드입니다.
for i in range(n):
for j in range(n):
print(i, j)
- 위 코드는 for 루프를 2번 사용하여 n x n 크기의 2차원 반복문을 만들고 있습니다. 이 경우 첫 번째 반복문에서 i 값이 1 증가할 때마다 두 번째 반복문은 n번 실행됩니다. 따라서 두 반복문의 실행 횟수는 n²번이 됩니다.
- 따라서 이 코드의 시간 복잡도는 O(n²)입니다. 즉, 입력 크기 n이 증가할 때, 실행 시간은 n²에 비례하여 증가합니다. 따라서 n이 커질수록 실행 시간이 급격하게 증가할 수 있습니다.
댓글