문제 해결 가능성이라는 이론적인 측면에서 알고리즘은 4가지의 조건(입출력, 명확성, 유한성, 유효성)을 모두 만족해야 한다(①-유효성, ②-명확성, ③-유한성, ④-입출력).
특히 입출력 조건은 0개 이상의 외부 입력과 하나 이상의 출력이 있어야 한다는 것으로, 외부 입력은 존재하지 않아도 무관하므로 보기 ④의 설명이 적절하지 못하다.
한편, 알고리즘의 실용적인 측면까지 고려한다면 알고리즘이 효율적이어야 한다는 조건도 필요하다.
주어진 문제의 종류와 조건 등의 다양성 때문에 범용적인 알고리즘 설계 기법은 존재하지 않으나, 비교적 간단하면서도 많은 부류의 문제에 적용 가능한 대표적인 설계 기법으로는 분할정복 방법(교재 2장), 동적 프로그래밍 방법(교재 3장), 욕심쟁이 방법(교재 4장)이 있다.
입력으로 사용되는 데이터의 크기(“입력 크기”)가 증가하면 그에 따라 당연히 수행 시간도 증가한다.
따라서 단순히 수행되는 단위 연산의 개수가 아닌 입력 크기 n에 대한 함수로서 시간 복잡도를 표현한다.
f(n)=2n3+3n2-n+10이라고 하고 g(n)=n3이라고 하자.
n>3에 대하여 f(n)≥2g(n)일 때 f(n)을 나타내는 점근적 표기법은?
1
f(n)=O(n3)
2
f(n)=Ω(n3)
3
f(n)=Θ(n3)
4
f(n)=o(n3)
정답입니다.
정답 : 2
3보다 큰 모든 입력 크기 n에 대해서 f(n)이 2g(n)보다 크거나 같다는 것은 결국 g(n)이 더 이상 작아질 수 없는 점근적 하한을 의미하고, 점근적 하한에 해당하는 표기법은 Big-omega이다.
참고로 Big-oh 표기법은 점근적 상한(f(n)≤cg(n)), Big-theta 표기법은 점근적 상하한(c1g(n)≤f(n)≤c2g(n))을 의미한다.
알고리즘의 시간 복잡도를 점화식으로 표현하였을 때 가장 효율적인 알고리즘에 해당하는 것은?
1
T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1)
2
T(n) = T(n-1) + Θ(n), T(1)=Θ(1)
3
T(n) = T(n/2) + Θ(1), T(1)=Θ(1)
4
T(n) = T(n/2) + Θ(n), T(1)=Θ(1)
정답입니다.
정답 : 3
각 보기에 해당하는 점화식의 폐쇄형을 차례대로 계산하면 Θ(nlogn), Θ(n2), Θ(logn), Θ(n)이 된다.
또한, O-표기 간의 연산 시간의 크기 관계에서 오른쪽에 해당할수록 상대적으로 효율성이 나쁜 것을 의미한다.
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)
따라서 Θ(nlogn), Θ(n2), Θ(logn), Θ(n) 중에서 가장 효율성이 좋은 것은 결국 O(logn)이며, 이에 해당하는 보기 ③의 점화식은 이진 탐색의 수행 시간을 나타낼 때 사용된다.
정리하기
[ 컴퓨터 알고리즘이란? ]
▶ 주어진 문제의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것
▶ 조건(입출력, 명확성, 유한성, 유효성) + 실용적 관점에서의 추가 조건(효율성)
▶ 생성 과정 : 설계 → 표현(기술) → 정확성 분석 → 효율성 분석
[ 알고리즘의 설계 ]
▶ 주어진 문제와 조건 등이 매우 다양하므로 모든/대부분 문제에 적용할 수 있는 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법이 있음
[ 알고리즘 분석 ]
▶ 정확성 분석: 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는지를 판단 → 수학적 기법을 사용해서 이론적으로 증명
▶ 효율성 분석: 공간 복잡도(알고리즘 수행에 필요한 메모리양), 시간 복잡도(알고리즘을 실행시켜 완료될 때까지 걸리는 시간)
▶ 시간 복잡도: 알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 표현 → 최악의 수행 시간을 입력 크기의 함수로 표현
[ 점근성능 ]
▶ 입력 크기 n이 무한히 커짐에 따라 결정되는 성능 → 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현 → 알고리즘의 수행 시간의 증가 추이를 나타내는 것으로 알고리즘의 우열 관계를 따질 때 용이
▶ 표기법 : ① “Big-oh” 점근적 상한 f(n) = O(g(n)), ② “Big-omega” 점근적 하한 f(n)=Ω(g(n)), ③ “Big-theta” 점근적 상하한 f(n)=Θ(g(n))
▶ O-표기 간의 연산 시간의 크기 관계 : O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)
[ 순환 알고리즘의 성능 ]
▶ 분할정복 방법을 적용한 알고리즘은 기본적으로 순환 알고리즘의 형태로 표현되고, 순환 알고리즘의 성능은 점화식으로 표현됨
▶ 기본 점화식과 폐쇄형
① T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)
② T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n2) → 퀵 정렬의 최악 수행 시간
③ T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn) → 이진 탐색의 수행 시간
④ T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → Θ(n)
⑤ T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → Θ(n)
⑥ T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn) → 퀵 정렬의 최선 수행 시간, 합병 정렬의 수행 시간
