[Algorithm] 알고리즘의 정의 및 조건

알고리즘(**algorithm)**의 정의

주어진 문제의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 유한개의 일련의 명령을 순서적으로 구성한 것

• 입출력 : 0개 이상의 외부 입력 → 1개 이상의 출력
• 명확성 : 각 명령은 모호하지 않고 단순 명확해야 함
• 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료
• 유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 함

순차 탐색

앞에서 부터 하나씩 뒤로 가면서 탐색한다

이진 탐색

알고리즘을 설계하고 만들고 테스트 및 분석하는 방법

• 설계
  • 상향식 설계
  • 하향식 설계
• 표현/기술
  • 일상 언어 단계 1, 단계 2, ...
  • 순서도 플로우차트 등
  • 의사코드
  • 프로그래밍 언어
• 정확성 검증
  • 수학적 증명
• 효율성 분석
  • 공간 복잡도
  • 시간 복잡도

알고리즘의 설계 기법

알고리즘을 효율적으로 설계할 때는 횟수를 적게, 시간을 짧게 하는 것을 고려하는 것이 좋다.

주어지는 문제나 속성, 조건 등이 다양하기 때문에 설계의 전략도 다양하다

대표적 알고리즘 설계 기법

• 분할 정복 divide and conquer
• 동적 프로그래밍 dynamic programming
• 욕심쟁이 greedy

알고리즘 분석

알고리즘의 정확성 분석

유효한 입력, 유한 시간 ⇒ 정확성 결과 생성 여부

다양한 수학적 기법을 사용해 이론적인 증명을 한다.

우리가 쓰는 대부분의 알고리즘은 이미 정확성 분석과 검증을 마친 상태이기 때문에 정확성보다는 효율성에 초점을 맞추는 것이 더 큰 변화를 줄 수 있다.

알고리즘의 효율성 분석

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정한다. 자원을 적게 쓰는 것이 효율적이다.
• 메모리 양을 기준으로 측정하는 것이 **공간 복잡도(Space Complexity)**이다. 공간 복잡도 = 정적 공간 + 동적 공간
• 수행 시간을 기준으로 측정하는 것은 **시간 복잡도(Time Complexity)**이다. 시간 복잡도 = f(n) = 단위연산 수행 횟수(입력 크기)

알고리즘의 시간 복잡도

알고리즘을 실행시켜 완료할 때까지 걸리는 시간으로, 알고리즘에서 수행되는 단위 연산의 수행 횟수의 합을 고려한다.

실제 수행 시간을 측정하는 방법은 컴퓨터 속도, 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 종속적이기 때문에 일반성이 결여된다.

따라서, 알고리즘의 단위 연산의 수행 횟수의 합으로 계산한다.

→ f(n) : 입력으로 제공되는 데이터의 크기나 대상의 개체가 많으면 수행 시간도 증가할 수 있기 때문에 단위 연산 개수의 합(f)에 입력 크기(n)도 함께 고려해야 한다.

⇒ 공간 복잡도는 계산하는 방법이 간단하기 때문에 보통은 크게 신경쓰지 않는 편이다. 더 복잡한 시간 복잡도를 더 신경써야 한다.

입력 데이터 상태에 종속적이기 때문에 최악수행시간을 시간복잡도로 고려한다.

• 평균수행시간
• 최선수행시간
• 최악수행시간

시간복잡도 구하는 방법

시간복잡도를 구할 때는 **비교연산(<,>,<=,>=), 교환연산(=)**을 중심으로 구한다

void Insertion(int n) {
	int key;
	for (int i = 1; i <= n - 1; i++) {  //(1)외부루프는 n-1회
		key = a[i];    //(2)외부루프에 의해 교환연산이 n-1회 일어남
		int j;
		for (j = i - 1; j >= 0; j--) {  //(3)내부루프는 최대 i회
			if (a[j] >key){       //(4)외부르프x내부루프에 의해 비교연산 최대 (n-1)+(n-2)...1=n(n-1)/2회 일어남.<-등차수열의 합
				a[j + 1] = a[j]; //(4-1)조건에 의해 교환연산이 최대 n(n-1)/2회
            }
			else{
				break;
            }
		}
		a[j + 1] = key;    //(5)외부루프에 의해 교환연산이 n-1회 일어남
	}
}

• 최악의 경우(역순으로 정렬되있음) =

1*(n-1) + 2*(n(n-1)/2) + 1*(n-1) = n^2+n-2 =   O(n^2)

(2)           (4,4-1)          (5)

• 최선의 경우(이미 정렬되있음) =

1*(n-1) + (n-1) + 1*(n-1) = 3n-3 = O(n)

(2)        (4)        (5)

점근성능의 표기법

점근성능이란?

입력 크기 n이 충분히 커질 때 결정되는 알고리즘의 성능으로, 점근적 상한 f(n) = O(g(n)), 점근적 하한 f(n)=Ω(g(n)), 점근적 상하한 f(n)=Θ(g(n)) 등을 사용해서 표기한다.

점근성능의 결정 방법

수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현한다.

• 수행시간의 정확한 값이 아닌 어림값을 사용한다.
• 수행시간의 증가 추세를 파악하는데 용이하다.
• 알고리즘의 우열 표현이 용이해진다.

점근성능의 표기법

Big-oh 점근적 상한

함수 f와 g를 각각 양의 정수를 갖는 함수라고 하고

어떤 양의 상수 c와 n0이 존재하여 모든 n≥n0에 대하여 f(n)≤c*g(n) 이면 f(n)=O(g(n))이다.