2장 알고리즘 소개(2) - 방통대, 알고리즘

학습개요

이번 강의에서는 앞으로 다룰 다양한 알고리즘에 적용될 기본적이고 핵심적인 개념으로, 알고리즘의 성능을 분석하고 점근성능으로 표기하는 방법을 중심으로 학습한다. 또한 순환 알고리즘의 개념과 이를 위한 점화식에 대해서도 살펴본다.

학습목표

• 알고리즘의 시간 복잡도의 개념을 이해하고 적용할 수 있다.
• 점근성능의 표기법의 종류와 개념을 이해하고 적용할 수 있다.
• 순환 알고리즘과 점화식의 관계 및 기본 점화식의 의미를 이해할 수 있다.
•  

주요용어

• 시간 복잡도(time complexity)-알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 정의되며, 입력 크기의 함수와 최악의 수행시간으로 표현
• -알고리즘을 실행시켜 완료할 때까지 걸리는 시간
• 공간 복잡도(space complexity)
• 알고리즘 수행에 필요한 총 메모리의 양(=정적 공간 + 동적 공간)
• 점근성능(asymptotic performance)-표기법: f(n) = O(g(n)) → 점근적 상한, f(n)=Ω(g(n)) → 점근적 하한, f(n)=Θ(g(n)) → 점근적 상하한
• -입력의 크기가 무한히 커짐에 따라 결정되는 알고리즘의 성능
• 순환 알고리즘(recursive algorithm, 재귀 알고리즘)-순환 알고리즘의 수행시간은 기본적으로 점화식 형태로 표현됨
• -알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 호출하여 수행하는 형태의 알고리즘
• 점화식(recurrence equation)- 점화식을 풀어서 구한 폐쇄형으로 성능 표현
  1. 알고리즘 분석
     1. ⦁ 알고리즘 분석 → 정확성 분석, 효율성 분석
     2. ⦁ 정확성 분석 → 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는 지를 수학적으로 증명하는 것
     3. ⦁ 효율성 분석 → 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정공간 복잡도 → 알고리즘 수행에 필요한 총 메모리의 양시간 복잡도 → 알고리즘의 수행시간
     4. ⦁ 알고리즘 수행시간 → 알고리즘의 각 단위 연산(문장)이 수행되는 횟수의 합입력 크기의 함수로 표현데이터의 입력 상태에 따라 달라짐 → 최악의 수행시간으로 표현
  2. 점근성능
     1. ⦁ 입력 크기가 무한히 커짐에 따라 결정되는 성능수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 단순하게 표현하는 방법 → 알고리즘 수행시간의 증가 추세를 나타내므로 알고리즘 간의 우열 표현/비교에 용이요소 → 시작
     2. ⦁ 표기법O-표기(“Big-oh”) → 점근적 상한 → 알고리즘의 최악의 수행시간에 해당Ω-표기(“Big-omega”) → 점근적 하한 → 최선의 수행시간에 해당Θ-표기(“Big-theta”) → 점근적 상한과 하한을 동시에 표시
     3. ⦁ O–표기의 함수 간의 크기 관계 → O(1) < O(logn) < O(n) < O(nlogn) < O(n) < O(n) < O(2)
     4. ⦁ 실용적인 계산 방법 → 알고리즘에 나타난 루프(반복문)의 반복횟수를 조사하여 최고 차수를 시간 복잡도로 취함
  3. 순환 알고리즘
     1. ⦁ 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 호출하여 수행하는 형태의 알고리즘수행시간은 점화식으로 표현되고, 이를 풀어서 폐쇄형으로 표시분할정복 방법의 적용된 알고리즘(이진 탐색, 퀵 정렬, 합병 정렬)은 기본적으로 순환 알고리즘 형태로 표현됨
     2. ⦁ 기본적인 점화식과 폐쇄형
        1. ① T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → T(n) = Θ(n)
        2. ② T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → T(n) = Θ(n) → 퀵 정렬의 최악 수행 시간
        3. ③ T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → T(n) = Θ(logn) → 이진 탐색의 수행 시간
        4. ④ T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → T(n) = Θ(n)
        5. ⑤ T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → T(n) = Θ(n)
        6. ⑥ T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → T(n) = Θ(nlogn) → 퀵 정렬의 최선 수행 시간, 합병 정렬의 수행 시간

---

1 알고리즘 분석

1-1 정확성분석

유효한 입력에 대해 유한 시간 내에 정확한 결과의 생성 여부

수학적 기법을 사용한 이론적인 증명 과정

📌 실제적으로는 학교에서 이 내용을 다루지 않음

1-2 효율성 분석

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정/평가
• 공간복잡도
  • 메모리의 양 = 정적공간 + 동적 공간
• 📌 시간복잡도
  • 수행시간 = 알고리즘의 실행에서부터 완료까지 걸리는 시간

컴퓨터에서 실행시켜 수행시간을 측정하는 방법?

• 실행 환경에 종속적이므로 일반성이 결여된 방법
  • 컴퓨터 속도, 구현에 사용된 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 따라 시간이 달라짐

알고리즘 수행시간 = 각 문장(연산)이 수행되는 횟수

• 수행시간에 영향을 미치는 요인
• 입력되는 데이터의 크기, 문제가 해결하려는 대상이 되는 개체의 수
  • 예) 리스트 원소의 개수, 행렬의 크기, 그래프의 정점의 수 등
• 입력데이터의 상태

입력크기 n이 커질수록 수행 시간도 증가

• 단순히 단위 연산이 수행되는 개수의 합으로 표현하는 것은 부적절
• 입력 크기 n의 함수 **f(n)**으로 표현
  • e.g f(n) = 2n^2, 3n + 20 n=10 250, n=100 2320

입력 데이터의 상태에 종속적

• 최선의 수행시간 : 말그대로 수행시간중 최소
• 📌 최악의 수행시간 : 말그대로 수행시간중 최악
  • 📌 알고리즘 수행시간은 최악의 수행시간으로 표기함

출근할때 최선 최악 평균 시간중 최악의 경우로 출근시간을 계산해야 하는 예시 사진

 

여러분이 집을 갈때 몇분을 생각하고 출근해야할까요? 못해도 최악인 89분 안에는 나와야 회사에 정상적으로 출근할 수 있다는 걸 알수있습니다.

 

SumAverage(A[], n)
{// A[0..n-1], n 입력 배열과 데이터의 개수
	sum = 0;            ---> 1
	i = 0;             ----> 1
	while(i<n){    --------> n + 1
		sum = sum + 1;     --> n
		i = i + 1;        ---> n		
	}
	average = sum / n;   --> 1
	print sum, average; ---> 1
}

 

 

T(n) = 3n + 5 —> 점근성능 O(n) Big-oh

이라고 표기하는것을 조금있다 배움

 

 

반응형

2 점근성능

입력크기 n 이 무한이 커짐에 따라 결정되는 성능

아래의 함수를 보자

왼쪽함수가 초기에는 더 큰값을 가지나 n이 커지면 커질수록

오른쪽 함수가 커지는 것을 확인할 수 있다

 

다음 함수를 보자 초기에는 상수 C인 200이 큰 비중을 차지하나

n이 커지면 커질수록 A의 비중이 커질 수 밖에 없다

이처럼 입력크기가 충분히 커짐에 따라 함숫값에 가장 큰 영향을 미치는 차수를 찾는 것 이다

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

e.g ) 2n^2 + 5n + 200 → n^2, 3n + 5 → n

위의 값이 정확한 값이 아닌 어림값이다, 하지만 수행시간의 증가 추세를 파악하는 것이 쉽다. 알고리즘 간의 우열을 따질 때 유용

점금성능의 표기법 - Big-oh 점근적 상한

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

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

 

다른거 볼 필요없이 빨간 함수만 보면된다 빨간함수인 f(n)이 무슨짓을 하더라도 최악일 수 밖에없는거다

점근성능의 표기법 - Big - omega 점근적 하한

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

어떤 양의 상수 C와 n_0이 존재하여 모든 n≥n_0 에 대하여 f(n) ≥ c * g(n) 이면 f(n) = 오메가(g(n)) 이다.

다른거 볼 필요없이 빨간 함수만 보면된다 빨간함수인 f(n)이 무슨짓을 하더라도 최선일 수 밖에없는거다

 

점금성능의 표기법 - Big-theta 점근적 상하한

다른거 볼 필요없이 빨간 함수만 보면된다 빨간함수인 f(n)이 무슨짓을 하더라도 최선과 최악 안에 있음으로 보다 정확한 알고리즘 일 수 밖에없는거다

총 정리하면 f(n)이 주어졌을때 O( ) 안에는 f(n)의 최고차항만 들어가면 된다는 말이다.

 

 

위의 사진들 처럼 n이 커질수록 별로다

3 순환알고리즘

BinarySearch (A[], key, Left, Right){
	if (Left > Right) return -1;
	mid = ( Left + Right ) / 2;
	if (A[mid]) == key return mid;
	else if (key < A[mid]) BinarySearch ( A, key, Left, mid -1 )
		else BinaraySearch(A, key, mid + 1, Right
}

• 입력 크기 n: 배열의 길이라고 생각할 수 있음.
• 한 번 비교(O(1)): 중간값(mid)을 계산하고, 그 값이 찾는 값인지 비교하는 데 O(1) 시간이 걸림.
• 문제를 절반으로 줄임: 찾는 값이 중간값보다 작으면 왼쪽 절반, 크면 오른쪽 절반으로 입력 크기를 절반으로 줄여서 재귀 호출함. 즉, 문제의 크기를 n → n/2로 줄임.
• O(1) (중간값 계산 + 비교)
• 이후 절반 크기로 재귀 호출: T(n/2)

동그라미 친 3개인 퀵정렬(최악의 경우), 이진탐색, 합병정렬 | 퀵정렬(최선의 경우) 만 알면 나머지는 쉽게 풀 수 있다고 한다.

허허글쎄요..