AL - 알고리즘과 시간복잡도

esc247·2023년 6월 19일

학교수업

CS

목록 보기

2/5

알고리즘

문제를 푸는 독특한 단계별 절차
- 문제(Problem) : 특정 과제, 해답을 찾으력고 물어보는 질문
- Parameter : 값이 지정되어 있지 않은 변수
  - 파라미터가 달려있는 문제 → 문제 패턴, 그 파라미터에 특정 값 지정하면 → 개별문제
  - 파라미터에 지정할 값 : 입력사례(Instance).
  - 해답(Solution) : 특정 입력사례에 대한 해답.
모든 Instance에 대해 Solution이 있어야 알고리즘
다음을 가진다
- Input
- Output
- Definiteness
  - 명확해야한다.
- Finiteness
  - 반드시 끝나야 한다.
- Effectiveness
  - basic and feasible(실현가능한).
  - Space Complexity
    - memory.
    - 최근엔 잘 고려안함.
  - Time Complexity
    - execution time.
  - 예시1) Sequential Search (순차검색) vs Binary Search (이분검색)
    - 둘 다 특정 원소를 주어진 배열 등에서 찾는 것이 목표이다.
    - 순차검색은 말 그대로 처음부터 하나씩 비교하며 찾는 것이다.
      - 크기가 n인 배열에서 비교를 n번 해야만 한다.
    - 이분검색은 배열이 정렬되어 있을 떄 사용한다.
      - 먼저 정중앙에 위치한 원소화 비교.
      - 같으면 끝, 중앙 원소보다 작으면 전반부, 크면 후반부에 원하는 값이 있다.
      - 해당 하는 부분에서 다시 이분검색 진행하고 이를 찾을 때까지 반복한다.
    - 크기가 n 일 떄
      - 순차검색은 n만큼 시간이 걸린다.
        
        $S(n) = S(n-1)+1=S(n-2)+1+1=....=n$
      - 이분검색은 $\log_{2}n$ 만큼 시간이 걸린다.
    - 만약 40억개의 원소가 있다면 순차탐색은 40억개를 모두 비교해야 하는데 이분검색은 33번만 하면 된다.
  - 예시2) 피보나치 수열
    - recurrence relation.
    - 단순하게 재귀 형식 그대로 코드를 작성하면 같은 계산을 중복해서 호출하기 떄문에 느리다.
    - $T(n)$ 을 n에 대한 재귀 나무구조의 항의 개수라 하면,
      - $T(n) > 2^{n/2}$

시간 복잡도 분석

단위 연산이 수행되는 횟수를 입력의 크기에 대한 함수로 구해 알고리즘의 효율성 분석.
배열 원소의 개수 n이 입력크기를 나타내는 간단한 척도.
입력크기를 기준으로 단위연산을 몇 번 수행하는지 구하는 것.
$T(n)$ : 일정 시간복잡도(every-case time complexity)
- 실행 횟수가 일정한 경우, 입력 크기 n에 대해서 알고리즘이 단위연산을 실행하는 횟수.
- 예시1) 배열 원소를 모두 더하기
  - for 루프를 n번 실행
  - $T(n) = n$
- 예시2) 교환 정렬
```
void exchage(int n, keytype S[])
{
	index i,j;
	for (i=1; i<=n-1 ; i++)
		for( j=i+1; j<=n; j++)
			if(S[j] < S[i])
				exchange S[i] and S[j];
	
}
```
  - $T(n) = (n-1) + (n-2) +...+1 =\frac{(n-1)n}{2}$
$W(n)$ : 최악 시간복잡도 (worst-case time complexity)
$A(n)$ : 평균 시간복잡도 (average-case )
$B(n)$ : 최선 시간복잡도 (best-case)
만약 $T(n)$ 이 존재하면
- $T(n) = W(n)= A(n)= B(n)$