알고리즘 2강 (알고리즘 소개)

학습개요

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

 학습목표

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

 주요용어

1. 시간 복잡도(time complexity)
   -알고리즘을 실행시켜 완료할 때까지 걸리는 시간
   -알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 정의되며, 입력 크기의 함수와 최악의 수행시간으로 표현
2. 공간 복잡도(space complexity)
   알고리즘 수행에 필요한 총 메모리의 양(=정적 공간 + 동적 공간)
3. 점근성능(asymptotic performance)
   -입력의 크기가 무한히 커짐에 따라 결정되는 알고리즘의 성능
   -표기법: f(n) = O(g(n)) → 점근적 상한, f(n)=Ω(g(n)) → 점근적 하한, f(n)=Θ(g(n)) → 점근적 상하한
4. 순환 알고리즘(recursive algorithm, 재귀 알고리즘)
   -알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 호출하여 수행하는 형태의 알고리즘
   -순환 알고리즘의 수행시간은 기본적으로 점화식 형태로 표현됨
5. 점화식(recurrence equation)
   - 함수의 한 값이 자신을 포함한 수식으로 다시 표현된 식
   - 점화식을 풀어서 구한 폐쇄형으로 성능 표현

 정리하기

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