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

순차 탐색 알고리즘으로 시간 복잡도 계산

순서 탐색 알고리즘

- 맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘이기에 순차 탐색이라는 이름이 붙어있다.

for(i=0; i<len; i++)

{

if(ar[i] == target)

return i;

}

위의 코드를 토대로 시간 복잡도를 분석해서 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구해보자.

일단, 이 알고리즘에서 사용된 연산자는 <, ++, == 이렇게 세 개이다. 이 연산자들이 얼마나 많이 수행이되는지를 분석하면 되는데...

이 질문에 답을 하고 분석을 진행해야 한다.

"어떠한 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘인가?"

탐색 알고리즘에서 값의 동등을 비교하는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

즉, 탐색 알고리즘에서의 핵심은 동등비교를 하는 비교연산에 있다. 비교연산의 수행횟수가 줄어들면 < 연산과 ++ 연산의 수행횟수도 줄어들고, 비교연산의 수행횟수가 늘어나면 < 연산과 ++ 연산의 수행횟수도 늘어나기 때문이다.

정리하면, 다른 연산들은 == 연산에 의존적이다.

따라서 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다. 

이렇듯 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야 한다. 그리고 그 연산을 중심으로 시간 복잡도를 계산해야 한다.

순차 탐색 알고리즘의 비교 연산횟수를 계산하는데... 순차 탐색 알고리즘은 운이 좋아서 찾고자 하는 값이 배열의 맨 앞에 저장되어 있으면 비교연산의 수행횟수는 1이 되고, 운이 없어서 찾고자 하는 값이 배열의 맨 마지막에 저장되어 있거나 찾고자 하는 값이 아예 저장되어 있지 않으면 비교연산의 수행횟수는 n이 된다. 

이렇듯 모든 알고리즘에는 가장 행복한 경우와 가장 우울한 경우가 각각 존재하며, 이를 전문용어로 '최선의 경우(Best Case)' 그리고 '최악의 경우(Worst Case)' 라 한다. 

그런데 알고리즘을 평가하는데 있어서 '최선의 경우'는 관심대상이 아니다. 어떠한 알고리즘이건 간에 최선의 경우는 대부분 만족할 만한 결과를 보이기 때문이다.

반면, 데이터의 수가 많아지면 '최악의 경우'에 수행하게 되는 연산의 횟수는 알고리즘 별로 큰 차이를 보인다. 따라서 알고리즘의 성능을 판단하는데 있어서 중요한 것은 '최악의 경우'이다.

평균적인 경우(Average Case) 는 시간 복잡도를 평가하는 정보로 의미를 지닌다. 하지만 문제는 이를 계산하는 것이 쉽지 않다는데 있다. 이를 계산하기 위해서는 다양한 이론이 적용되어야 하고, 분석에 필요한 여러 가지 시나리오와 데이터를 현실적이고 합리적으로 구성해야 하는데, 이는 쉽지 않은 일이다.

기본이 되는 다음 질문에 답을 하기조차 쉽지가 않다. 

"무엇이 평균적인 상황인가?"

때문에 '평균적인 경우' 라고 주장하기 위해서는 다양한 자료들이 광범위하게 수집되어야 한다. 결국 일반적인 알고리즘의 평가에는 논란의 소지가 거의 없는 '최악의 경우(Worst Case)' 가 선택될 수 밖에 없다.

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

계산할 것이 사실상 없다. 이 알고리즘의 흐름을 소스코드상에서 이해했다면, 다음 사실을 바로 파악할 수 있기 때문이다.

"데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는(비교연산의 홧수는) n이다."

따라서 순차 탐색 알고리즘의 '데이터 수 n에 대한 연산홧수의 함수 T(n)'은 다음과 같다.

T(n) = n        // 최악의 경우를 대상으로 정의한 함수 T(n)

이처럼 최악의 경우는 생각보다 쉽게, 코드의 분석을 통해서 구할 수 있는 경우도 많다.

순차 탐색 알고리즘의 시간 복잡도 : 평균적인 경우(Average Case)

평균적인 경우의 연산횟수 계산을 위해서 다음과 같이 두 가지를 가정한다.

1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정한다.

2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다.

탐색 대상이 존재하지 않는 경우의 연산 횟수         n

탐색 대상이 존재하는 경우의 연산 횟수                n/2

그런데 탐색 대상이 배열에 존재하지 않는 경우와 존재하는 경우의 확률이 각각 50%이니 다음과 같이 이 둘을 하나의 식으로 묶어야 한다.

1/2씩 곱해서 더한 이유는 탐색 대상이 존재하지 않을 확률과 존재할 확률이 각각 50%이기 때문이다. 

순차 탐색 알고리즘의 평균적인 경우의 시간 복잡도 함수:     T(n) = 3/4n

※ 최악의 경우에 비해서 상대적으로 시간 복잡도를 구하는 것이 쉽지 않다는 사실에 주목해야 한다. 뿐만 아니라 평균적인 경우의 시간 복잡도 함수는 신뢰도가 높지 않다. 그 이유는 앞서 정의한 두 개의 가정을 뒷받침할 근거가 부족하기 때문이다.

프로그램의 성격에 따라서 그리고 데이터의 성격에 따라서 배열에 탐색 대상이 존재할 확률은 50%보다 높을 수도 있고 높지 않을 수 도 있는데 이러한 부분이 전혀 고려되지 않았다. 

때문에 평균적인 경우의 시간 복잡도는 '최악의 경우'의 시간 복잡도보다 신뢰도가 낮다.

그래서 '최악의 경우'를 시간 복잡도의 기준으로 삼는 이유다!!!

성능분석 방법 중 최소한으로 필요한 수학 함수

        지수식

        로그식

시간 복잡도(Time Complexity) 와 공간 복잡도(Space Complexity)

그저 잘 동작하는 자료구조와 알고리즘을 찾는 것이 목적이라면 기능별로 자료구조와 알고리즘을 하나씩만 알아도 된다.

하지만 잘 동작하는 것은 물론이거니와 좋은 성능까지 보장받기를 원한다면, 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다.

모든 경우에 있어서 항상 우월한 성능을 보이는 만능 키와 같은 자료구조와 알고리즘은 존재하지 않기 때문이다. 

알고리즘을 평가하는 두 가지 요소

1. 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느릴까?

2. 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓸까?

이렇듯 하나는 '속도'에 관한 것이고 다른 하나는 '메모리의 사용량'에 관한 것인데, 속도에 해당하는 알고리즘의 수행시간 분석결과를 가리켜 '시간 복잡도(Time Cimplexity)' 라 하고, 메모리 사용량에 대한 분석결과를 가리켜 '공간 복잡도(Space Complexity)' 라 한다.

메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘이라 할 수 있다. 그런데 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 준다.

대게는 속도에 관심이 더 많고, 또 중요한 요소로 판단되기 때문이다. 

물론 특정 알고리즘에 대해서 상대적인 우월성을 입증해야 하는 경우에는 메모리의 사용량도 함께 고려가 되지만, 이미 검증이 끝난 알고리즘의 적용을 고려하는 경우에는 속도에 초점을 두어 적합성 여부를 판단하게 된다.

속도를 측정하는 방법

시계를 가져다 놓고 수행시간을 재고 있을 수는 없다. 혹 시간을 잴 수 있어도 큰 의미를 부여하기 어렵다.

처리해야 할 데이터양의 변화에 따른 속도의 증가 및 감소의 정도도 알아야 하는데, 이를 위해서 조건을 달리하여 수백 번, 수천 번 실행해가면서 시간을 잴 수 는 없는 일이기 때문이다. 그래서 알고리즘의 수행속도를 평가할 때는 다음과 같은 방식을 취한다.

1. 연산의 횟수를 센다.

2. 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n) 을 구성한다.

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

즉, 알고리즘 별 연산횟루를 함수 T(n)의 형태로 구성하면 그래프를 통해서 데이터 수의 변화에 따른 연산횟수의 변화 정도를 한눈에 파악할 수 있으며, 이로 인해서 둘 이상의 알고리즘을 비교하기가 용이해진다.

보라색의 알고리즘보다는 빨간색의 알고리즘이 좋다. 

그러나 빨간색의 알고리즘과 같이 안정적인 성능을 보장하는 알고리즘은 보라색의 알고리즘에 비해서 구현의 난이도가 높은 편이다. 따라서 데이터의 수가 많지 않고 성능에 덜 민감한 경우라면 구현의 편의를 이유로 보라색의 알고리즘을 선택하기도 한다.

※ 알고리즘의 정답은 없는 것이 아니라 상황에 맞게 답을 내려야 한다. 구현보다 중요한 것은 종합적으로 사고하고 판단하는 능력이다.