Chapter01. 윤성우의 열혈 자료구조(성능검사, 순차탐색)

자료구조는 수학을 기반으로한 학문이다.

그러므로 자료구조는 이론을 바탕으로 구현을 직접 경험하는 것이 올바른 공부방법이다.

구현을 바탕으로 이론을 공부하면 재대로된 공부방법이 아니므로 다시 한번 보자.

 

자료구조 학습에 있어서 기억할 것 두 가지

- 자료구조의 모델을 그림으로 우선 이해해야 한다.

(글로만 책에서 보여주는것이 전부 라고 생각하지 말고 거기에 없는 다양한 케이스들을 그림으로 그려봐야 한다.) 

- 구현이 가능해야만 의미가 있는 것은 아니다.

(능동적으로 코드 공부를 해라. 책에 나와있는 코드를 가리고 직접 넣던지,, 등등)

 

Chapter 01. 자료구조와 알고리즘의 이해

01-1 자료구조(Data Structure)에 대한 기본적인 이해

이 책은 기본적으로 C언어의 문법을 알고 난 후 보는게 도움이 된다.

 

자료구조 - 프로그램이란 데이터를 표현 하는 것이다. (표현에는 저장의 의미가 포함된다.) (데이터의 표현 및 저장방법)

알고리즘 - 표현된 데이터를 처리 하는 것이다.  (문제의 해결 방법)

 

자료구조와 알고리즘은 밀접한 관계를 갖는다.

자료구조에 따라서 알고리즘은 달라지고, 알고리즘은 자료구조에 의존적이다.

 

01-2 알고리즘의 성능분석 방법

이 방법은 자료구조의 성능분석 방법으로도 이용이 가능하므로 알고리즘에 국한되어 생각하지 말자.

자료구조는 크게 선형 자료구조, 비선형 자료구조로 나뉜다.

 

선형 자료구조는 비교적 쉬우나 비선형 자료구조는 비교적 어렵다.

이 성능분석 방법은 비선형 자료구조를 공부할때 더 많이 사용하고 비선형 자료구조를 공부할때 이 챕터를 다시 공부하게 될것이다.

 

성능분석을 하려면 수학적 배경지식을 필요로 한다.

지수식과 로그식이 필요로 하고

지수식 = y = 2^x

로그식 = y = log2(x)

 

x 축이 데이터의 갯수,

y 축이 그 수의 데이터를 연산하는데 있어서 특정 알고리즘을 적용을 하여 그 데이터를 처리하는데 걸리는 시간

이라고 가정하고 나온 그래프가 p.17의 그림01-2 그래프 이다.

 

알고리즘의 성능이 로그식 그래프에 따르면 좋은 성능이고 지수식 그래프에 따르면 성능이 좋지않은 알고리즘 이다.

 

 

시간 복잡도 & 공간 복잡도 1

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

- 시간 복잡도(time complexity) -> 얼마나 빠른가? (cpu에게 얼마나 부담을 주는가?)

- 공간 복잡도(space complexity) -> 얼마나 메모리를 적게 쓰는가? (보조적인 역할로 생각 메모리는 10~20퍼정도)

시간 복잡도를 더 중요시 한다.

 

시간 복잡도의 평가 방법

- 중심이 되는 특정 연산의 횟수를 세어서 평가를 한다.

- 데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

말 그대로 연산의 횟수를 통해서 알고리즘의 빠르기는 판단한다.

 

알고리즘의 수행 속도 비교 기준

- 데이터의 수가 적은 경우의 수행 속도는 큰 의미가 없다.

- 데이터의 수에 따른 수행 속도의 변화 정도를 기준으로 한다. (데이터의 수가 늘어날때 패턴이 중요하다.)

 

알고리즘의 수행속도 비교

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

자료구조는 어찌 보면 구현보다 중요한 것은 종합적으로 사고하고 판단하는 능력이다.

 

순차 탐색(Linear Search)알고리즘과 시간 복잡도 분석의 핵심요소

#define _CRT_SECURE_NO_WARNINGS
#include 

int LSearch(int ar[], int len, int target)
{
int i;
for (i = 0; i < len; i++)
{
if (ar[i] == target)
return i;
}

return -1;
}

int main(void)
{
int arr[] = { 3, 5, 2, 4, 9 };
int idx = LSearch(arr, sizeof(arr) / sizeof(int), 4);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);

return 0;
}

위의 예제는 c언어를 공부하면서 한 번 정도는 구현해 봤을법한 순차 탐색 알고리즘이다.

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

 

"위의 알고리즘엔 <, ++, == 이렇게 세 개의 연산자가 사용되었다. 하지만 어떠한 연산을 적게 수행하는 탐색 알거리즘이 좋은 탐색 알고리즘이겠는가?"

 

바로 값의 동등을 비교하는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다. 즉, 탐색 알고리즘에서의 핵심은 동등비교를 하는 비교연산에 있다. 비교연산의 수행횟수가 줄어들면 <, ++ 연산의 횟수도 줄어들고 반대로 늘어나면 나머지 두 연산의 수행횟수가 늘어난다. 따라서 다른 연산들은 == 연산에 의존적이다.

주변연산자(<, ++)의 연산횟수는 중심이되는 연산자(==)의 연산횟수에 의존적이다 (공식은 아니나, 힌트로 생각해라)

그리고 중심 연산자를 중심으로 시간복잡도를 분석하면 된다.

 

알고리즘의 성능을 위한 시간복잡도를 평가할 경우에는 worst case를 기준으로 한다. best case의 경우는 관심대상이 아니다. 평균의 경우(Average Case) 를 기준으로 하는게 가장 현실적이나 증명이 어렵다.

best case      =    T(n) = 1

worst case    =    T(n) = n

 

평균적인 경우(Average Case)

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

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

 

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

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

 

대상이 존재하지 않을 확률과 존재할 확률이 각각 50% 이기 때문에 1/2씩 곱해주어야 한다.

n x (1/2) + (n/2) x (1/2) = (3/4)n

이로써 순차 탐색 알고리즘의 평균적인 경우의 시간 복잡도 함수는 다음과 같다

T(n) = (3/4)n

 

그러나 평균적인 경우의 시간 복잡도 함수는 신뢰도가 높지 않다. 우리가 가정을 세워서 만든 식이고 실제로는 존재할 확률과 존재하지 않을 확률이 달라질수도 있다.

그러므로 평균적인 경우는 최악의 경우의 시간 복잡도 보다 신뢰도가 낮다. 그러므로 '최악의 경우'를 시간 복잡도의 기준으로 삼는 이유이다.