알고리즘의 이해(1)

참고문서 - 윤성우의 열혈 자료구조

1차 작성 - 2016/03/04 (이글루스에서 옮김)

 

알고리즘을 평가하는 요소

시간복잡도 – 어떤 알고리즘이 더 빠르고 느린지 속도에 관한 것

공간복잡도 – 메모리를 적게 쓰고 많이 쓰는 지와 같은 메모리 사용량에관한 것

최적의 알고리즘은 메모리를 적게 쓰고 속도가 빠른 것

일반적으로는 속도에 초점을 둔다 속도에서의 기준은 연산 횟수를 들 수 있다.

 

책에서는 비교연산 즉 ‘==’ 값의 동등을 비교하는 연산을 적게 수행하는탐색알고리즘이 좋은 것이라고 나타나 있다

Ex)

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

{

   If( ar[i] == target )       // 알고리즘의 복잡도를 분석할 수 있는 연산 부분

     return;

}

알고리즘의 성능 판단 – 최악의 경우로 비교한다

이유: 평균적인 경우로 판단해야 맞는다고 생각하기 쉽지만 실제로 평균을계산하거나 판단하기가 쉽지 않다 그리고 최악의 경우에 수행되는 연사의 횟수가 최선의 경우보다 더 큰 차이를 보이므로 대조하여 분석하기 쉽다.

부연 설명: 이를 평균적으로 계산하기 위해서는 다양한 이론이 적용되어야하고 분석에 필요한 여러 가지 시나리오와 데이터를 현실적이고 합리적으로 구성해야 정확한 시뮬레이션이 되는데 시간과 비용이 이를 감당하기 쉽지 않으므로쉽게 판단 가능한 최악의 경우로 비교하는 것이다.

• 의문 – 최악의 경우로만 비교할 경우 생기는부작용은 없는가??  확률적인 느낌이다.. 정답은 없을 듯

 

빅-오 표기법

빅오 – 성능분석의 도구

시간복잡도라는 함수 T(n)에서 가장 영향력이 큰 부분이 어디인가는따지는 것

함수 T(n)은 알고리즘의 (비교)연산 횟수를 다항식으로 표현 한 것

보통 T(n)은 다항식으로n^2+2n+2 라고 할 때 최고차항 차수 n^2가 빅오가 된다.

• 의문: 빅오를 구하는 이유는 무엇일까? 실제 알고리즘의 복잡도는 어떻게 구하고 판단해야 하는 가? 그 분석예를 알아 볼 순 없는가?

• 빅오는 비교하는 도구로 생각하지 복잡도 공부는 전공공부를 따로 하자 (알고리즘 과목)

 

다항식의 차수로 나타내는 이유는 빅오는 X-Y 좌표평면의 그래프와같다

X축은 데이터의 개수, Y축은 시간을 나타내는데 빅오의 O(n^2)는 결국 f(x) = n^2인 이차 방정식 그래프와 같다. 즉 X축(데이터 수)의 증가 에 따라 Y축(시간 or 연산횟수)의 증가를 보여주는 그래프의 형태나 패턴을 나타내는것과 같다

 

 정리하면‘데이터의 수의 증가’에 따른 ‘ 연산횟수의 증가 형태를 표현 한 것’ 이 빅오이다.

• 질문: 빅오를 알아야 하는 이유는 무엇인가? 성능이겠지... 그리고 성능비교를 위해 근데 위 그림은 다시 공부하자

 

결과적으로 if구문이나 ‘==’와같은 조건 비교를 적게 써야 한다 (for문과 같은 반복문 포함)

데이터의 수가 많은 경우 순차검색보다 이진 트리 검색의 경우가 더 빠르다   

이중 for문으로 돌려야 하는 경우 순차접근을 사용할 수 있지만 데이터가 순서대로 정렬되어 있고 조건비교를 할 수 있는 경우 이진검색 또는 다른 방법으로 더 빠른 성능 속도를 낼 수 있는지 고민해 볼 수 있어야 한다.

-----------------------------------------------------------------------------------------------------------------------

알고리즘은 아직 논할만큼 충분한 공부를 못했다 (전공책 한번만이라도 처음부터 끝까지 읽어보자... 인터넷 검색은 단편조각만 제공한다)