Big O 표기법: 기본 개념

2.1 Big O 표기법의 정의.

Big O 표기법은 수학적 표기법이야. 알고리즘의 실행 시간이나 자원 소비가 입력 크기에 따라 어떻게 바뀌는지를 설명하는 데 사용돼. 이는 알고리즘의 확장성과 데이터 양이 늘어날 때 성능이 어떻게 변하는지를 측정하는데 도움을 줘.

Big O는 상수와 덜 중요한 구성 요소를 무시하면서 알고리즘의 가장 중요한 부분에 집중하여 장기적인 동작을 분석하는 데 중점을 두지.

기본 표기법:

O(1) — 상수 복잡도:

• 알고리즘 실행 시간이 입력 데이터 크기에 영향받지 않아.
• 예: 배열 요소를 인덱스로 접근.

O(n) — 선형 복잡도:

• 알고리즘 실행 시간이 입력 데이터 크기에 따라 선형적으로 변해.
• 예: 배열의 모든 요소를 간단히 순회.

O(log n) — 로그 복잡도:

• 알고리즘 실행 시간이 입력 데이터 크기 증가에 따라 로그 단위로 늘어나.
• 예: 정렬된 배열에서 이진 탐색.

O(n^2) — 이차 복잡도:

• 알고리즘 실행 시간이 입력 데이터 크기에 따라 제곱으로 증가해.
• 예: 버블 정렬, 삽입 정렬.

O(2^n) — 지수 복잡도:

• 알고리즘 실행 시간이 입력 데이터 크기에 따라 지수 단위로 늘어나.
• 예: 완전 탐색으로 배낭 문제 해결.

2.2 Big O 표기법의 해석.

Big O 표기법을 어떻게 해석하고 사용할까?

상수와 덜 중요한 구성 요소 무시:

Big O는 함수의 성장 양상을 설명하며, 상수와 덜 중요한 구성 요소를 무시해. 예를 들어, O(2n)과 O(3n)은 O(n)으로 해석돼.

알고리즘 비교:

Big O를 통해 알고리즘을 비대칭 효율성으로 비교할 수 있어. 예를 들어, O(n log n) 알고리즘은 큰 데이터의 경우 O(n^2) 알고리즘보다 더 효율적이야.

최악의 경우 분석:

Big O는 보통 알고리즘의 최악의 경우 실행 시간을 분석하는 데 사용돼, 최대 복잡성을 평가할 수 있게 해주지.

상수 무시.

상수와 덜 중요한 구성 요소 무시

예제 1:

두 함수를 고려해보자:

• f(n) = 3n + 2
• g(n) = 5n + 1

두 함수 모두 선형 복잡도를 가져, 각 함수의 지배적인 항은 n이니까. 따라서 두 함수는 상수와 추가 항의 차이에도 불구하고 O(n)으로 해석돼.

예제 2:

두 함수를 고려해보자:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

두 함수 모두 이차 복잡도를 가져, 지배적인 항은 n^2이니까. 두 표현식 모두 다른 항과 계수의 차이에도 불구하고 O(n^2)으로 해석돼.

2.3. 알고리즘 비교

1. 매우 큰 데이터 엑세스에서의 알고리즘 비교

예제 1:

• 알고리즘 A는 O(n^2)의 시간 복잡도를 가져.
• 알고리즘 B는 O(n log n)의 시간 복잡도를 가져.

작은 n 값에서는 알고리즘 A가 상수 때문이라도 더 빠를 수 있지만, 큰 n 값에서는 알고리즘 B가 훨씬 빠르게 되지, 로그 성장이니까, 이차적으로 증가하지 않아서.

예제 2:

• 알고리즘 X는 O(n)의 시간 복잡도를 가져.
• 알고리즘 Y는 O(1)의 시간 복잡도를 가져.

알고리즘 Y는 항상 더 빠르겠지, 입력 데이터 크기가 어떤지와 상관없이, O(1)이란 알고리즘 실행 시간이 입력 데이터 크기에 영향을 받지 않는다는 뜻이니까.

2. 최악의 경우 분석

예제 1:

버블 정렬 알고리즘은 최악의 경우 O(n^2)의 시간 복잡도를 가져, 배열이 역순으로 정렬된 경우 말이야. 이는 배열의 각 요소에 대해 다른 모든 요소와 비교하며, 필요하다면 교환해야 한다는 의미지.

예제 2:

이진 탐색은 최악의 경우에는 O(log n)의 시간 복잡도를 가져. 이는 최악의 경우에도 요소를 찾는 데 필요한 단계 수가 배열 크기에 따라 로그적으로 증가한다는 뜻이니까, 아주 효율적이지.

3. 성능과 확장성에 대한 영향

예제 1:

데이터 처리 알고리즘이 두 개 있다면, 하나는 O(n^2)의 시간 복잡도, 또 다른 하나는 O(n log n)의 시간 복잡도를 가질 때, 데이터 크기를 1000개에서 10,000개로 증가시키면 성능 차이가 뚜렷하게 나타나.

• O(n^2) 알고리즘은 10,000개 요소에 대해 대략 100,000,000번의 연산을 수행할 거야.
• O(n log n) 알고리즘은 10,000개 요소에 대해 약 40,000번의 연산을 수행할 거야.

예제 2:

O(2^n) 복잡도를 가진 알고리즘을 생각해 보자. 입력 데이터 크기를 10에서 20 요소로 증가시키면 연산 수가 지수 단위로 증가해.

• n = 10: 2^10 = 1024 연산.
• n = 20: 2^20 = 1,048,576 연산.

이는 지수 복잡도가 큰 n 값에서는 실행 가능성을 빠르게 넘어서버리게 되는 걸 보여주지.