자료구조 : 데이터의 표현 및 저장방법
선형구조 : 리스트, 스택 큐
비선형구조 : 트리, 그래프
파일구조 : 순차파일, 색인파일, 직접파일
단순구조 : 정수, 실수, 문자, 문자열
알고리즘 : 표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법
예를 들면
int arr[10] {1, 2, ...}; //초기화되었다고 가정
for(idx= 0; idx <10; idx++)
sum += arr[idx];
여기서 자료구조는 배열이고 반복문은 알고리즘이라고 할 수 있다.
즉 자료구조가가 결정이 되어야 그에 따른 효율적인 알고리즘을 결정할 수 있다.
시간 복잡도(Time Complexity) : 알고리즘의 수행시간 분석결과를 가리킨다
공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량에 대한 분석결과를 가리킨다.
즉 이 두가지의 요소로 알고리즘을 평가할 수 있다.
일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다.
실행속도를 측정하는 방법은 연산의 횟수를 세는것이다.
처리해야할 데이터의 수 n개의 대한 연산횟수 T(n)을 구성한다.
즉 데이터의 수를 입력하면 연산의 횟수가 계산되는 식을 구성한다는 뜻이다.
식을 구성하면 데이터 수의 증가에 따른 연산 횟수의 변화 정도를 판단이 가능하다.
그래프를 데이터의 수 변화에 따른 연산횟수의 변화 정도를 한눈에 파악할 수 있고, 둘 이상의 알고리즘을 비교하기가 용이해진다.
알고리즘은 상황에 맞게 답을 내려야 한다.
순차 탐색(Linear Search)알고리즘과 시간 복잡도 분석의 핵심요소
#include <stdio.h>
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()
{
int arr[] = {3, 5, 2, 4, 9};
int idx;
idx = LSearch(arr, sizeof(arr)/ sizeof(int), 4);
if(idx==-1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스 : %d\n", idx);
idx = LSearch(arr, sizeof(arr)/ sizeof(int), 7);
if(idx==-1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스 : %d\n", idx);
return 0;
}
==============실행결과===============
타겟 저장 인덱스 : 3
탐색 실패비교하는 ==연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.
즉 비교연산의 수행횟수가 줄어들면 < 연산과 ++연산의 수행횟수도 줄어들게된다.
정리하면 , 다른 연산들은 ==연산에 의존적이다.
따라서 ==연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다.
알고리즘의 시간복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야하고, 그 연산을 중심으로 시간 복잡도를 계산해야 한다.
위의 예제의 수행횟수를 찾아보자.
모든 알고리즘에는 예를 들어 한번에 찾은경우를 최선의 경우(best case), 예를 들어 없거나 마지막부근에서 찾은 경우를 최악의 경우(worst case)라 한다.
만약 위 예제에 찾는 값이 저장이 안되어 있으면 비교 연산의 횟수는 n이 된다.
알고리즘을 평가하는데 최선의 경우는 관심대상이 아니고, 최악의 경우를 따져야 한다.
순차 탐색 알고리즘의 시간복잡도 계산 : 최악의 경우
데이터수가 n개 일때, 최악의 경우에 해당하는 연산횟수는 n이다.
즉 함수로 나타내면 '데이터의 수 n에 대한 연산횟수의 함수 T(n)'
T(n) = n //최악의 경우를 대상으로 정의한 함수(T(n))
순차 탐색 알고리즘의 시간 복잡도 계산 : 평균적인 경우
가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정
가정 2 . 배열의 첫 요소 부터 마지막 요소 까지, 탐색 대상이 존재할 확률은 동일하다.
탐색 대상이 존재하지 않을 경우의 연산횟수 : n
탐색 대상이 존재하는 경우의 연산횟수 : n/2
n * 1/2 * n/2 * 1/2 = 3/4 *n
1/2를 곱한 이유는 존재하지 않을 확률과 존재할 확률이 각각 50%이기 때문이다.
순차 탐색 알고리즘의 평균적인 경우의 시간복잡도 함수는
T(n) = 3/4 *n이다.
평균적인 경우의 시간 복잡도 함수는 신뢰도가 높지 않다 . 가정을 뒷받침할 근거가 부족하기 때문이다.
그래서 최악의 경우를 시간복잡도의 기준으로 잡아야 한다.
이진 탐색(Binary Search)알고리즘
순차 탐색보다 훨씬 좋은 성능을 보이는 알고리즘이다.
하지만 다음 조건을 만족해야 한다.
"배열에 저장된 데이터는 정렬되어 있어야 한다 "
즉 , 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. (정렬의 기준과 방식과는 관계없다).
때문에 성능이 덜한 순차 탐색 알고리즘도 우리에겐 유용한 알골지ㅡㅁ이다.
이진탐색 알고리즘의 첫번째시도.
1. 배열 인덱스의 시작과 끝은 0과 8이다.
2. 0과 8을 합하여 그 결과를 2로 나눈다.
3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.
즉 배열의 중앙에, 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘의 첫번째 시도이다.
첫번째 시도를 통해 저장이 안되어 있음을 확인하고, 두번째 시도를 진행한다.
이진탐색 알고리즘의 두번째시도
1. arr[4]에 저장된 값과 탐색 대상의 값의 대소를 비교한다.
2.대소의 비교결과가 작으면 해당 인덱스 값보다 작은 인덱스 값의 기록되어 있으므로 해당 인덱스 값을 제외한 0~ 해당인덱스 -1 값으로 범위를 제한한다.
3. 0과 인덱스-1을 더하여 2로 나눈다. 이때 나머지는 버린다.
4. 2로 나눠서 얻은 결과를 인덱스 값에 넣어 arr[인덱스값]에 저장된 값이 3인지 확인한다.
두 번째 시도에서 볼 과정은 탐색의 대상이 반으로 줄었다는 것이다.
이는 배열에 데이터가 정렬된 상태로 저장되었기 때문에 가능한 일이며, 이것이 이진 탐색 알고리즘의 핵심이다.
만약 여기에도 저장이 안되어 있으면 두번째 시도를 반복한다.
이렇듯 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다.
즉 이진탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다. 때문에 순차 탐색 알고리즘에 비해 좋은 성능을 보인다.
이진탐색 알고리즘을 구현하기 위해 탐색의 형태를 다시 살펴본다.
인덱스의 시작값과 마지막값을 각각 first와 last라 칭하고. 살펴보면
결국에 first와 last값은 만나게된다 (같아지게된다).
first와 last의 값이 같아지면 탐색의 대상이 없다는 것이 아니고 탐색의 대상이 하나 남아있음을 뜻ㄱ핟ㄴ다.
이진탐색은 first<last인 상황에서는 물론 first = last에서도 계속 되어야 한다. 때문에 이진 탐색 알고리즘은 다음과같은 형태로 반복문이 구성된다.
while(first <= last)
{
//이진 탐색 알고리즘의 진행
}
결론은
first가 last보다 큰 경우 탐색은 종료된다. 그리고 이렇게 종료가 되었다는 것은 탐색에 실패했음을 뜻한다.
#include <stdio.h>
int BSearch(int ar[], int len, int target)
{
int first = 0; //탐색 대상의 시작 인덱스 값
int last = len-1; //탐색 대상의 마지막 인덱스 값
int mid;
while(first <= last)
{
mid = (first + last) / 2; //탐색 대상의 중앙을 찾는다.
if(target == ar[mid])
{
return mid; //탐색 완료
}
else //타겟이 아니라면 탐색의 대상을 반으로 줄인다.
{
if(target <ar[mid]
last = mid-1;
else
first = mid+1;
}
}
return -1; //찾지 못했을 때 반환되는 값 -1
}
int main()
{
int arr[] = {1,3,5,7,9};
int idx;
idx = BSearch(arr,sizeof(arr)/ sizeof(int), 7);
if(idx ==-1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스 : %d \n", idx);
idx = BSearch(arr,sizeof(arr)/ sizeof(int), 4);
if(idx ==-1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스 : %d \n", idx);
return 0;
}
==================================실행결과=====================================
타겟 저장 인덱스 : 3
탐색 실패
first와 last에 +1과 -1을 하는 이유는 탐색에 실패했을때 first가 last보다 커져 반복문의 종료을 위해 뿐만 아니라 ,
mid에 저장된 배열의 요소는 이미 탐색을 한 것인데 다시 포함해서 탐색하기 때문에 불필요하다.
이진 탐색 알고리즘의 시간복잡도 계산을 해보자.
위 예제를 보면 최악의 경우 기준으로는
데이터의 수가 n개 일때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 될까?
예를들어 n이 8이면
연산횟수는 총 2로 3번을 나눈다.
8 4 2 1
즉 8이 1이 될때까지 2로 나눈 횟수는 3회 , 따라서 비교연산 3회 진행
데이터가 1개 남았을 때, 이 때 마지막으로 비교연산 1회 진행
즉 n으로 일반화를 하면
n이 1이 되기까지 2로 나눈 횟수 k, 따라서 비교연산 k회 진행
데이터가 1개 남았을때, 마지막으로 비교연산 1회 진행
즉 이진탐색 알고리즘의 최악의 경우의 시간복잡도는
T(n) = k +1 이다 .
이게 끝이 아니고, k를 구하는 문제가 남아있다.
n이 1이 되기 까지에 2로나눈 횟수가 k이니, n과 k에 대한 관한식을 세울 수 있다.
n * (1 /2)^k = 1
이제 이 식을 k에 관한 식으로 나타내기 위해 정리한다.
n * (1/2)^k = 1
n * 2^-k = 1
n = 2^k
이제 남은 정리는 양변에 밑에 2인 log를 취한다.
n= 2^k
log_2 n = log_2 2^k
log_2 n = k log_2 2
log_2 n = k
즉 k는 log_2 n이다.
따라서 이진탐색 알고리즘의 최악의 경우에 대한 T(n)은 다음과 같다.
T(n) = log_2 n 이다.
최악의 경우의 비교연산 횟수는 k+1이다. T(n) = log_2 n +1이라 생각할 수있는데
+1은 중요하지 않다. 중요한 것은 데이터의 수 n이 증가함에 따라서 비교연산의 횟수가 로그적으로 증가한다는 사실이다.
식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다.
즉 n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않다.
빅-오 표기법(Big-Og Notation)
사실 데이터의수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않다.
빅-오라는 것은 영향력이 큰 부분이 어딘가를 따지는 것인데, 이때 사용되는 표기법에 대문자 O, 그러니까 큰 O가 사용되기 때문에 빅-오라고 하는것이다.
T(n) = n^2 +2n +1
->
T(n) = n^2 +2n
->
T(n) = n^2
로 나머지를 생략할 수 있다. n^2에 비해 영향이 모두 적기 떄문이다.
이를 확인 할 방법은 n에 직접 숫자를 넣는 방법인데 10, 100, 10,000 , 100,000 이런식으로 넣어보는 것이다.
즉 큰수가 대입할수록 n^2가 차지하는 비율이 매우 커지고 2n+1의 영향력이 줄어들기 때문에 간략화를 할 수있다.
이를 빅 -오 표기법으로 표현하면 다음과 같다.
O(n^2)
"빅-오 오브 n^2 " 라고 읽는다
정리하면 T(n) = n^2 +2n +1의 빅오는 n^2이며, 이는 n의 증가 및 감소에 따른 T(n)의 변화 정도가 n^2형태를 띰을 뜻한다.
단순하게 T(n)이 다항식으로 표현되는 경우 , 최고 차항의 차수가 빅-오가 된다.
즉
T(n)= a_m n^m + a_m-1 n^m-1 +... + a_1 n^1 + a_0 -> O(n^m)
다항식으로 표현된 시간 복잡도 함수 T(n)에서 실제로 큰 의미를 갖는 것은 '최고차항의 차수(n^m)'이다.
빅-오는 데이터 수의 증가에 따른 연산횟수의 증가형태(패턴)을 나타내는 표기법이라, 차수 앞에 있는 정수는 몇이든 빅-오의 관점에서는 동일하다.
즉 다음이 의미하는 바는 O(log n)이다.
"데이터 수의 증가에 따른 연산횟수의 증가 형태를 좌표평면상에 그려놓으면, 증가하는 추세가 둔화되는 형태를 띤다. 다시 말해서 로그 그래프와 유사한 형태를 띤다."
대표적인 빅-오를 설명하자면
O(1)
이를 상수형 빅-오라 한다. 이는 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다. 예를 들어 여ㅑㄴ산의 횟수가 데이터 수에 상관없이 3회 진행되는 알고리즘일지라도 O(3)이라 하지 않고 O(1)이라 한다. 이렇듯 O(1)에는 연산횟수가 고정인 유형의 알고리즘을 대표하는 의미가 담겨있다.
O(log n)
이를 로그형 빅-오라 한다. 이는 '데이터의 증가율'에 비해서 '연산횟수 증가율'이 훨씬 낮은 알고리즘을 의미한다. 이는 매우 바람직한 유형이다.참고로 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만, 그 차이는 알고리즘의 성능관점에서는 매우 미미하기 때문에 대부분의 경우에 있어서 무시가 된다.
O(n)
이를 선형 빅-오라 한다. 이는 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.
O(n log n)
이를 선형로그형 빅-오 라한다. 이는 데이터 수가 두배로 늘때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘을 뜻한다. n과 log n을 곱한 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다.
O(n^2)
이는 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기가 부적적한데, 이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 달리 말하면 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.
O(n^3)
데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 이는 삼중으로 중첩된반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이 역시 그냥 적용하기에는 무리가 있는 알고리즘이다.
O(2^n)
이를 지수형 빅-오라 한다. 이는 사용하기에 매우 무리가 있는, 사용하는 것 자체가 비현실적인 알고리즘이다. '지수적 증가'라는 , 매우 무서운 연산횟수의 증가를 보이기 때문이다. 처음 알고리즘을 개발했을 때 이러한 성능을 보인다면, 개선의 과정을 거쳐서 현실적이 연산횟수를 보이는 알고리즘으로 수정되어야 한다.
지금까지 설명한 빅-오 표기들의 성능(수행시간, 연산횟수)의 대소를 정리하면 다음과 같다.
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)
T(n) = n //순차 탐색 알고리즘의 T(n)함수
T(n) = log_2 n +1 //이진 탐색 알고리즘의 T(n) 함수
이것을 빅-오 표기법으로 전환하면
O(n)
O(log n)
위의 그래프를 참고하면 , 성능의 차이도 어느정도 인지 알 수 있다.
성능을 비교하는 실험의 원칙은 다음과 같다.
최악의 경우를 대상으로 비교하는 것이 목적이니 탐색의 실패를 유도한다.
탐색의 실패가 결정되기까지 몇번의 비교연산이 진행되는지를 센다.
데이터의 수는 500, 5000, 50000일 때를 기준으로 각각 실험한다.
O(n)의 연산횟수는 계산하기 쉽다.
O(log n)의 연산횟수는 이진탐색 알고리즘을 대상으로 비교연산을 진행해 알아보자.
#include <stdio.h>
int BSearch(int ar[], int len, int target)
{
int first =0;
int last =len-1;
int mid;
int opCount = 0; //비교연산의 횟수를 기록
while(first <= last)
{
mid = (first + last ) / 2;
if(target == ar[mid])
{
return mid;
}
else
{
if(target < ar[mid])
last = mid-1;
else
first = mid+1;
}
opCount +=1; //비교 연산의 횟수 1증가
}
printf("비교연산횟수 : %d \n", opCount); //탐색 실패 시 연산횟수 출력
return -1;
}
int main()
{
int arr1[500] = {0, }; //모든 요소 0으로 초기화
int arr2[5000] = {0, }; //모든 요소 0으로 초기화
int arr3[50000] = {0, }; //모든 요소 0으로 초기화
int idx;
//배열 arr1을 대상으로 , 저장되지 않은 정수 1을 찾으라고 명령
idx = BSearch(arr2, sizeof(arr2)/sizeof(int), 1);
if(idx == -1)
printf("탐색 실패 \n\n");
else
printf("타겟 저장 인덱스 : %d \n", idx);
//배열 arr2을 대상으로 , 저장되지 않은 정수 1을 찾으라고 명령
idx = BSearch(arr1, sizeof(arr1)/sizeof(int), 1);
if(idx == -1)
printf("탐색 실패 \n\n");
else
printf("타겟 저장 인덱스 : %d \n", idx);
//배열 arr3을 대상으로 , 저장되지 않은 정수 1을 찾으라고 명령
idx = BSearch(arr3, sizeof(arr3)/sizeof(int), 1);
if(idx == -1)
printf("탐색 실패 \n\n");
else
printf("타겟 저장 인덱스 : %d \n", idx);
return 0;
}
즉 실행결과의 근거로 순차 탐색 알고리즘과 이진 탐색 알고리즘의 연산횟수를 정리하면
| n | 순차 탐색 연산 횟수 | 이진 탐색 연산 횟수 |
| 5000 | 5000 | 13 |
| 50000 | 50000 | 16 |
빅-오는
데이터 수의 증가에 따른 연산횟수 증가율의 상한선을 표현한 것 이다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 연결리스트2 (0) | 2021.02.13 |
|---|---|
| 링크드리스트1 (0) | 2021.02.12 |
| 배열 기반의 리스트(List)2 (0) | 2021.02.09 |
| 배열 기반의 리스트(List)1 (0) | 2021.02.08 |
| 재귀 함수 (0) | 2021.02.05 |
