Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않다. 

그래서 Big-Oh 표기법을 사용한다.

빅-오라는 것은 함수 T(n) 에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다. 

이때 사용되는 표기법에 대문자 O, 그러니까 큰 O가 사용되기 때문에 빅-오라고 하는 것이다.

  이것을   이렇게 근사치(approximation) 식을 구성해도 문제가 되지 않는다. 

그 이유는 표를 통해서    에서   이 차지하는 비율을 확인하면 알 수 있다.

 이 차지하는 비율의 증가를 나타내는 표

표에서 보이듯이  이 차지하는 비율은 절대적이다.   이 조금만 증가해도 이내  이 차지하는 비율은 99%를 넘어선다.

따라서,  은  으로 간략화 할 수 있다.

그리고 이것을 빅-오 표기법으로 표현하면 다음과 같다.

         =>            빅-오 오브         =>            

정리하면 함수  의 빅오는  이며, 이는  의 증가 및 감소에 따른  의 변화 정도가  의 형태를 띰을 의미한다.

예를 들면,

                                      ▶                 

                                     ▶                

                    ▶                

그리고 이것을 일반화화면 다음과 같다.

                 ▶                

즉, 다항식으로 표현된 시간 복잡도 함수 T(n)에서 실제로 큰 의미를 갖는 것은  '최고차항의 차수' 라는 이야기다.

※ 빅-오는 "데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)" 을 나타내는 표기법이다.

 이것은 다음과 같이 이해해야 옳다.

- "데이터 수의 증가에 따른 연산횟수의 증가 형태를 좌표평면상에 그려놓으면, 증가하는 추세가 둔화되는 형태를 띤다. 즉, 로그 그래프와 유사한 형태를 띤다."

빅-오는 성능 분석에 좋은 도구가 된다.

대표적인 빅-오

'데이터 수의 증가'에 따른 '연산횟수의 증가 형태를 표현한 것'이 빅-오이다 보니, 데표적인 빅오 표기가 존재한다. 이것들은 알아둘 필요가 있다.

상수형 빅-오라 한다. 이는 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘이다. 연산횟수가 고정인 유형의 알고리즘을 대표한다.

로그형 빅-오라 한다. 이는 '데이터 수의 증가율'에 비해서 '연산횟수의 증가율' 이 훨씬 낮은 알고리즘을 의미한다. 따라서 매우 바람직한 유형이다. 

참고로 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만, 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무기가 된다.

선형 빅-오라 한다. 이는 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.

선형로그형 빅-오라 한다. 이는 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다. n과 logn을 곱한 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다.

데이터 수의 제곱에 해당하는 연산홧수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기가 부적절하다.

이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 

즉, 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.

데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.

이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이 역시 그냥 적용하기에는 무리가 있는 알고리즘이다.

지수형 빅-오라 한다. 이는 사용하기에 매우 무리가 있는... 사용한다는 것 자체가 비현실적인 알고리즘이다.

'지수적 증가' 라는, 매우 무서운 연산횟수의 증가를 보이기 때문이다. 처음 알고리즘을 개발했을 때 이러한 성능을 보인다면, 개선의 과정을 거쳐서 현실적인 연산횟수를 보이는 알고리즘으로 수정되어야 한다.

빅-오 표기들의 성능(수행시간, 연산횟수) 의 대소를 정리

   <    <     <     <    <    <  

이진 탐색 알고리즘은 순차 탐색 알고리즘보다 훨씬 좋은 성능을 보이는 알고리즘이다.

하지만 배열을 대상으로 이진 탐색 알고리즘을 적용하기 위해서는 다음의 조건을 만족해야만 한다.

"배열에 저장된 데이터는 정렬되어 있어야 한다."

즉, 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다 (정렬의 기준 및 방식과는 관계없다).

만약 길이가 9인 배열이 있다고 가정하면...

이진 탐색 알고리즘의 첫 번째 시도:

1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.

2. 0과 8을 합하여 그 결과를 2로 나눈다.

3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.

즉, 배열의 중앙에, 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘이다.

이진 탐색 알고리즘의 두 번째 시도:

1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교한다.

2. 대소의 비교결과는 arr[4] > 3 이므로 탐색의 범위를 인덱스 기준 0~3으로 제한한다.

3. 0과 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.

두 번째 시도 과정에서 주의 깊게 살펴볼 것은 탐색의 대상을 반으로 줄였다는 사실이다. 이는 어디까지나 배열에 데이터가 정렬된 상태로 저장되었기 때문에 가능한 일이다.이것이 바로 이진 탐색 알고리즘의  핵심이다.

이진 탐색 알고리즘의 세 번째 시도:

1. arr[1]에 저장된 값 2와 탐색 대상인 3의 대소를 비교한다.

2. 대소의 비교결과는 arr[1] < 3 이므로 탐색의 범위를 인덱스 기준 2~3으로 제한한다.

3. 2와 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.

이렇듯 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복할 뿐이다. 하지만 세 번째 시도를 진행하면서 탐색 대상인 3을 찾게 되니, 이로써 탐색은 마무리가 된다.

이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다. 때문에 순차 탐색 알고리즘에 비해 좋은 성능을 보인다.

위의 이진 탐색 알고리즘에서 last = mid-1; 과 first = mid+1; 에 감소와 증가가 없다면 어떻게 될까?

값을 하나 빼거나 더해서 그 결과를 변수 last와 first에 저장하지 않으면, mid에 저장된 인덱스 값의 배열요소도 새로운 탐색의 범위에 포함이 된다. 그런데 이는 불필요한 일이다. mid의 배열요소에 탐색 대상이 저장되어 있는지 검사가 이미 끝난 상태이기 때문이다.

그런데 더 큰 문제가 존재한다. 무엇이냐면... 

문제는 탐색의 대상이 배열에 존재하지 않는 경우... 무한루프를 형성하며 프로그램이 종료되지 않는다는 것이다.

탐색의 대상이 배열에 존재하지 않을 경우 first에 저장된 값이 last보다 커져서 반복문을 탈출할 수 있어야 하는데, 위와 같이 코드를 수정하고 나면 결코 first에 저장된 값은 last 보다 커질수 없다 (last는 first보다 작아질 수 없다). 

때문에 무한루프를 형성하게 되는 것이다.

감소나 증가를 하지 않는다면...기본적으로 세 변수에 저장된 인덱스 값은 항상 다음의 식을 만족하도록 알고리즘이 디자인된다.

감소나 증가를 뺀다면, mid에 저장된 값을 가감 없이 first 또는 last에 저장하는 것이 전부이다. 그래서 first는 결코 last보다 커질 수 없고, last는 결코 first보다 작아질 수 없다.

이진 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우(Worst Case)를 기준

우선, 연산횟수를 대표하는 연산이 무엇인지 찾아야 한다.

그런데 이 역시 탐색 알고리즘이니 순차 탐색 알고리즘과 마찬가지로 == 연산을 연산횟수를 대표하는 연산으로 볼 수 있다.

"데이터의 수가 n개일 때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 되는가?"

- 데이터의 수 n이 n/2, n/4, n/8... 이렇게 줄어서 1이 될 때까지 비교연산을 한 번씩 진행하고, 마지막으로 n이 1일 때 비교연산을 한 번 더 진행한다. 그리고 그것이 탐색 대상이 존재하지 않는 최악의 경우의 비교연산 횟수이다. 그러니까 데이터의 수가 8개였다면 8,4,2,1 이렇게 줄어드니 총 4회 비교연산이 진행된다.

위와 같이 답을 내릴 수 있다. 하지만! 이 정도의 정보는 성능의 분석 및 비교에 사용할 수 없다.

이 정도의 정보를 가지고 앞서 다른 탐색 알고리즘과의 객관적 성능 비교는 가능하지 않다.

위의 데이터의 수가 8개인 상황에서의 비교연산 횟수는 다음과 같이 정리할 수 있다.

# 8이 1이 되기까지 2로 나눈 홧수 3회, 따라서 비교연산 3회 진행.

# 데이터가 1개 남았을 경우, 이때 마지막으로 비교연산 1회 진행.

↓↓↓↓↓ 다시 정리하면...

# n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행.

# 데이터가 1개 남았을 경우, 이때 마지막으로 비교연산 1회 진행.

이로써 비교연산의 횟수를 구했으니, 최악의 경우에 대한 시간 복잡도 함수 T(n)은 다음과 같이 정리된다.

# 최악의 경우에 대한 시간 복잡도 함수 :        T(n) = k + 1

2로 나눈 횟수 k 구하기.

n이 1이 되기까지 2로 나눈 횟수가 k이니, n과 k에 관한 식을 다음과 같이 세울 수 있다.

     =>     n에 8을, k에 3을 대입하면 식은 성립된다. ex) 8 * pow((1/2.0), 3)  하면 1이 나올 것이다. 이 식은 2로 몇 번을 나누어야 1이 되는가에 대한 답을 주는 수식이다.

     ▶         ▶   

※  과 같기 때문에..  이런식이 나올 수 있다.

이제 정리된 최종 수식의 양 변에 밑이 2인 로그를 취한다.

  ▶  ▶   ▶ 

이렇듯 k는 log2n 이다. 따라서 이진 탐색 알고리즘의 최악의 경우에 대한 시간 복잡도 함수 T(n) 은 다음과 같다.

그런데.. 위에 +1이 있었다. 하지만 +1은 중요하지 않다. 

중요한 것은 데이터의 수 n이 증가함에 따라서 비교연산의 횟수가 로그적(logarithmic)으로 증가한다는 사실이다.

"식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다."

즉, n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않다.