(자료구조 강의) Chapter 03 - 알고리즘 성능 분석

첫 번째 강의에서 순차 탐색 알고리즘과 이진 탐색 알고리즘의 성능을 비교하기 위해 데이터 1,000,000개를 가지고 테스트 했습니다.

 

데이터를 탐색하는데 걸리는 시간이 바로 나와서 확인하기 편했지만 모든 코드에 테스트 코드를 붙여서 테스트를 하려니 번거롭습니다.

또한 다음과 같은 의문이 들어 정확한 비교, 분석이라고 하기 애매합니다.

 

❝ 데이터가 1,000,000개가 아니라 10,000,000개 일 때는 얼마나 차이가 나요? ❞

❝ 탐색 데이터가 배열 첫 번째에 있으면 이진 탐색보다 선형 탐색이 더 빠른 거 아닌가요? ❞

 

알고리즘을 정확하게 비교하는 방법

 

우리는 알고리즘을 비교하고 분석하는 방법 중 하나인 빅-오 표기법을 알아볼겁니다.

 

다른 방법은 빅-오메가, 빅-세타가 있는데 다음과 같은 특징을 가집니다.

 

• 빅-오: 최악의 상황을 가정하여 분석
• 빅-오메가: 최선의 상황을 가정하여 분석
• 빅-세타: 평균적인 상황을 가정하여 분석

 

❝ 아니 당연히 평균적인 상황을 가정해서 분석해야지, 최악의 상황만 가지고 분석하는 건 너무 극단적인 거 아닌가요? ❞

 

평균적인 상황을 고려하여 분석하는게 합리적이라는 생각이 들지만 다음과 같은 이유로 계산이 어렵습니다.

 

1. 평균적인 경우의 연출이 어렵다
2. 평균적인 경우임을 증명하기 어렵다.
3. 평균적인 경우는 상황에 따라 달라진다.

 

그에 비해 최악의 경우는 늘 동일합니다. 최선의 경우는 연산이 빨리 끝날테니 크게 신경 쓰지 않아도 됩니다.

 

이런 이유로 우리는 최악의 경우일 때를 가정하여 분석해보겠습니다.

 

선형 탐색 알고리즘의 최악의 경우

이 경우는 탐색 대상인 데이터가 배열의 마지막에 존재할 경우입니다. (탐색 대상이 존재하지 않는 경우도 마찬가지 입니다.)

 

 

여기서 알 수 있는 사실은 선형 탐색의 경우 최악의 경우가 데이터의 개수에 정비례 한다는 것입니다.

10개의 배열에서 최악의 경우는 10번을 검사하기 때문입니다.

 

일반화 시키면 다음과 같은 결론을 알 수 있습니다.

 

길이가 n인 배열에서 선형 탐색 알고리즘의 최악의 경우는 n번 모두 검사하는 경우이다.

 

이를 빅-오 표기법으로 O(n)이라 하고 "빅오 오브 n" 이라 읽으면 됩니다.

 

 

이진 탐색 알고리즘의 최악의 경우

이진 탐색 알고리즘은 배열을 계속 반으로 쪼개면서 탐색 범위가 1개가 될 때 까지 탐색을 하는 경우입니다.

 

 

식으로 표현해보면 위와 같습니다. k를 구하면 최악의 경우 데이터가 n개일 때 몇 번 연산을 하는 지 알 수 있습니다.

 

위와 같은 과정을 통해 k는 log₂n이라는 식을 도출했습니다.

 

이를 빅-오로 표기하면 O(log₂n)가 되며, 데이터의 개수가 n개일 때 연산 횟수가 밑이 2인 로그함수에 비례 합니다.

 

다음은 빅-오를 데이터 수와 연산 횟수 관계를 그래프로 나타낸 것입니다.

 

데이터 수가 많아져도 연산횟수가 적은 O(1), O(log₂n) 두 가지가 좋아 보입니다.

O(1)은 연산 횟수가 1번이라는 뜻이 아니라 데이터 수와 상관 없이 일정한 연산 횟수를 가진 알고리즘을 의미합니다.

 

 

빅-오의 수학적 정의

선형 탐색, 이진 탐색 알고리즘을 통해 시간 복잡도와 빅-오에 대해 알아보았습니다. 그런데 n, log₂n 처럼 깔끔하게 식이 나오지 않고 n² +  n + 10 이런 결과가 나온다면 O(n² + n + 10) 라고 써야할까요?

 

빅-오의 수학적 정의는 다음과 같습니다.

 

두 개의 함수 f(n)과 g(n)이 주어졌을 떄, 모든 n ≥ K에 대하여 f(n) ≤ Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면, f(n)의 빅-오는 O(g(n)이다. 

 

음... 말이 너무 어렵습니다.

 

위 예시 빅-오의 실질적인 의미는 다음과 같습니다.

n² + n + 10이 아무리 연산 횟수의 증가율이 크다 해도 증가율 패턴이 n²을 넘지 못한다. 따라서 n² + n + 10의 빅-오는 O(n²)이다.

 

마지막으로 빅-오의 수학적 정의를 이용해 판별하는 과정을 보고 마치겠습니다.

 

"두 개의 함수 f(n)과 g(n)이 주어졌을 때"
    -> 두 개의 함수 f(n) = n² + n + 10, g(n) = n²이 주어졌을 때

"모든 n ≥ K에 대하여"
    -> 모든 n ≥ 12에 대하여

"f(n) ≤ Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면"
    -> n² + n + 10 ≤ 3000n²을 만족하는 3000(C)과 12(K)가 존재하니

"f(n)의 빅-오는 O(g(n))이다."
    -> n² + n + 10의 빅-오는 O(n²)이다.