방송대 광고
알고리즘의 대표적인 설계 기법이 아닌 것은?
1
회귀분석 방법
2
욕심쟁이 방법
3
동적 프로그래밍 방법
4
분할정복 방법
정답입니다.
정답 : 1
문제의 종류와 조건 등의 다양성 때문에 범용의 알고리즘 설계 기법은 존재하지 않으나, 비교적 간단하면서도 많은 부류의 문제에 적용 가능한 대표적인 설계 기법으로는 분할정복 방법(교재2장), 동적 프로그래밍 방법(교재3장), 욕심쟁이 방법(교재4장)이 있다.
알고리즘의 시간 복잡도는 무엇의 함수로 표현하는가?
1
입력 데이터의 값
2
입력 데이터의 크기
3
프로그램 코드의 길이
4
프로그램에 사용된 동적 변수의 개수
정답입니다.
정답 : 2
입력으로 사용되는 데이터의 크기(“입력 크기”)가 증가하면 당연히 수행 시간도 증가한다. 따라서 단순히 수행되는 단위 연산의 개수가 아닌 입력 크기의 함수로서 시간 복잡도를 표현한다.
Q3
f(n)=2n3+3n2-n+10이라고 하고 g(n)=n3이라고 하자. n>3에 대하여 f(n)≥2g(n)일 때 f(n)을 나타내는 점근적 표기법은?
1
f(n)=O(n^3)
2
f(n)=Ω(n^3)
3
f(n)=Θ(n^3)
4
f(n)=o(n^3)
정답입니다.
정답 : 2
3보다 큰 모든 입력 크기 n에 대해서 f(n)이 2g(n)보다 크거나 같다는 것은 결국 작아지지 않는다는 점근적 하한을 의미하고, 점근적 하한에 해당하는 표기법은 Big-omega이다. 참고로 Big-oh 표기법은 점근적 상한(f(n)≤cg(n)), Big-theta 표기법은 점근적 상하한(c1g(n)≤f(n)≤c2g(n))을 의미한다.
Q4
알고리즘의 시간 복잡도를 점화식으로 표현하였을 때 가장 효율적인 알고리즘에 해당하는 것은?
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)이 된다.
다음과 같은 알고리즘의 시간 복잡도를 빅오 표기로 나타내시오.
서술형 주관식 입력칸
O(n^2)
정답과 비교해 보세요.
정답 : 설명참고
정답&해설: O(n2)
실용적으로 알고리즘의 시간 복잡도를 계산하기 위해서는 주어진 알고리즘에서 시간이 많이 걸리는 부분, 즉 루프의 반복횟수를 조사하면 된다.
위의 알고리즘의 경우 바깥 for문(i)의 경우에는 n-1회 반복하고, 안쪽 for문(j)의 경우에도 n-1회 반복을 하게 되는데, 바깥 for문의 각 i에 대해서 안쪽 for문의 j가 n-1회 반복하기 때문에 전체적으로는 n2-2n+1만큼 반복한다.
점근 성능은 알고리즘 수행 시간의 최고차항(여기서는 n2)에만 의존하기 때문에 결국 시간 복잡도 O(n2)이 된다.
정리하기 정리하기
알고리즘의 설계
주어진 문제와 조건 등이 매우 다양하므로 알고리즘의 일반적인 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법이 있다.
알고리즘 분석
정확성 분석 : 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는 지의 여부를 판단
효율석 분석 : 알고리즘 수행에 필요한 컴퓨터의 자원의 양을 측정 → 공간 복잡도, 시간 복잡도 → 시간 복잡도 : 알고리즘을 실행시켜 완료될 때까지 걸리는 시간으로, 알고리즘에서 수행되는 단위 연산의 총 횟수로 표현 → 최악의 경우 수행 시간을 입력 크기의 함수로 표현
점근 성능
입력 크기 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(n^2) < O(n^3) < O(2^n)
기본 점화식과 폐쇄형
T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)
T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n^2)
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)