자료구조란 무엇인가?
프로그램이란 데이터를 표현(자료구조) 하고, 그렇게 표현된 데이터를 처리(알고리즘) 하는 것이다
알고리즘의 성능분석 방법
수학과 관련해서 알고 있어야 할것
지수,로그 + 지수함수,로그함수
지수와 로그 지수함수와 로그함수 지수함수와 로그함수의 관계
kyoun.tistory.com
시간 복잡도 & 공간 복잡도
▶ 알고리즘을 평가하는 두 가지 요소
시간 복잡도(time complexity) -> 얼마나 빠른가?
공간 복잡도(space complexity) -> 얼마나 메모리를 적게 쓰는가?
시간 복잡도를 더 중요시 한다.
▶ 시간 복잡도의 평가 방법
중심이 되는 특정 연산의 횟수를 세어서 평가를 한다.
데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.
▶ 알고리즘의 수행 속도 비교 기준
데이터의 수가 적은 경우의 수행 속도는 큰 의미가 없다.
데이터의 수에 따른 수행 속도의 변화 정도를 기준으로 한다
순차 탐색 알고리즘과 시간 복잡도
최악의 경우와 최상의 경우
시간 복잡도와 공간 복잡도 각각에 대해서 최악의 경우와 최상의 경우를 구할 수 있다.
▶ 순차 탐색 상황 1: 운이 좋은 경우
배열의 맨 앞에서 대상을 찾는 경우
만족스러운 상황이므로 성능평가의 주 관심이 아니다!
‘최상의 경우(best case)’라 한다.
▶ 순차 탐색 상황 2: 운이 좋지 않은 경우
배열의 끝에서 찾거나 대상이 저장되지 않은 경우
만족스럽지 못한 상황이므로 성능평가의 주 관심이다!
‘최악의 경우(worst case)’라 한다.
평균적인 경우(Average Case)
▶ 가장 현실적인 경우에 해당한다.
일반적으로 등장하는 상황에 대한 경우의 수이다.
최상의 경우와 달리 알고리즘 평가에 도움이 된다.
하지만 계산하기가 어렵다. 객관적 평가가 쉽지 않다.
▶ 평균적인 경우의 복잡도 계산이 어려운 이유
‘평균적인 경우’의 연출이 어렵다.
‘평균적인 경우’임을 증명하기 어렵다.
‘평균적인 경우’는 상황에 따라 달라진다
순차 탐색 최악의 경우 시간 복잡도
순차 탐색 평균적 경우 시간 복잡도
∙ 가정 1 탐색 대상이 배열에 존재하지 않을 확률 50% -> n이라함
∙ 가정 2 배열 첫 요소부터 마지막 요소까지 탐색 대상 존재 확률 동일
∙ 탐색 대상이 존재하지 않는 경우의 연산횟수는 n
∙ 가정 1에 의해서 탐색 대상이 존재하는 경우의 연산횟수는 n/2
이진 탐색 알고리즘의 소개
▶ 이진 탐색 알고리즘의 첫 번째 시도:
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인지 확인한다
▶ 이진 탐색 알고리즘의 핵심
이진 탐색 알고리즘의 구현
∙ first와 last가 만났다는 것은 탐색 대상이 하나 남았다는 것을 뜻함!
∙ 따라서 first와 last가 역전될때까지 탐색의 과정을 계속!
int BSearct(int arr[], int len, int target)
{
int first = 0;
int last = len - 1;
int mid;
while (first <= last)
{
mid = (first + last) / 2;
if (target == arr[mid]) //중앙이 타켓이라면
{
return mid;
}
else // 타겟이 아니라면 탐색 대상을 반으로 줄인다
{
if (target < arr[mid]) //
{
last = mid - 1;
}
else // target > arr[mid]
{
first = mid + 1;
}
}
}
return -1;
}
-1 혹은 +1을 추가하지 않으면 first <= mid <=last가 항상 성립이 되어,
탐색 대상이 존재하지 않는 경우 first와 last의 역전 현상이 발생하지 않는다!
이진 탐색 알고리즘 최악의 경우 시간 복잡도
while (first <= last)
{
mid = (first + last) / 2;
if (target == arr[mid]) //중앙이 타켓이라면
{
return mid;
}
else
시간 복잡도 계산을 위한 핵심 연산은? == 연산자
따라서 == 연산자의 연산 횟수를 기준으로 시간 복잡도를 결정할 수 있다.
▶ 데이터의 수가 n개일 때 비교 연산의 횟수
∙ 처음에 데이터 수가 n개일 때의 탐색과정에서 1회의 비교연산 진행
∙ 데이터 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행
∙ 데이터 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행
∙ 데이터 수를 반으로 줄여서 그 수가 n/8개일 때의 탐색과정에서 1회 비교연산 진행
. . . . . n 이 얼마인지 결정되지 않았으니,
이 사이에 도대체 몇 번의 비교연산이 진행되는지 알 수가 없다 ! . . . . .
∙ 데이터 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회의 비교연산 진행
▶ 이러한 표현 방법으로는 객관적 성능 비교 불가!
▶ 비교 연산의 횟수의 예
∙ 8이 1이 되기까지 2로 나눈 횟수 3회, 따라서 비교연산 3회 진행
∙ 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행
▶ 비교 연산의 횟수의 일반화 (위 예를 일반화)
∙ n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행
∙ 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행
▶ 비교 연산의 횟수의 1차 결론!
∙ 최악의 경우에 대한 시간 복잡도 함수 T(n)=k+1
n이 1이 되기까지 2로 나눈 횟수가 k 이니, n과 k에 관한 식을 다음과 같이 세울수 있다
[n이 1이 될라면 , k번 1/2 해야 한다]
이 수식에 당황하지 말자
2로 나누는 것은 1/2를 곱하는 것과 같다는 단순한 사실만 알면 이해할 수 있는 수식이다
▶ 이제 결론
- 함수 T(n)= k+1 이므로…
▶ 그러나 +1은 생략하여
※ 시간 복잡도의 목적은 n의 값에 따른 T(n)의 증가 및 감소의 정도를 판단하는 것이므로 +1은 생략 가능!
빅-오 표기법(Big-Oh Notation)
▶ T(n) 에서 실제로 영향력을 끼치는 부분을 가리켜 빅-오(Big-Oh)라 한다
▶ n 의 값에 따른 T(n)의 증가 및 감소의 정도를 판단하는 것이 목적 +1은 생략 가능!
▶ 2n도 근사치 식의 구성에서 제외시킬수 있음을 보인 결과, n이 증가함에 따라 2n+1이 차지하는 비율은 미미해진다.
단순하게 빅-오 구하기
순차 탐색 알고리즘 vs. 이진 탐색 알고리즘
'프로그래밍 > 자료구조' 카테고리의 다른 글
| 6. 스택(Stack) (0) | 2019.06.07 |
|---|---|
| 5. 원형 연결 리스트 3 (원형 + 양방향) (0) | 2019.06.06 |
| 4. 연결 리스트 2 (연결리스트 + 더미노드 + 정렬삽입) (0) | 2019.06.05 |
| 3. 연결리스트 1 (ADT + 배열기반 연결리스트) (0) | 2019.06.05 |
| 2. 재귀(Recursion) (0) | 2019.06.04 |