알고리즘에 대한
정의
로 틀린 것은?
1) 외부에서 제공되는 입력 자료가 있어도 좋고 없어도 관계없다.
2) 알고리즘으로 작성된 프로그램은 어느 순간에는 반드시 종료해야 한다.
3) 출력은 그 결과가 있어도 좋고 없어도 상관없다.
4) 알고리즘에서 제시된 명령문의 의미는 명확해야 한다.
알고리즘을 분석하는 방법 중
알고리즘 계산 시간의 계산
을 위하여 명령 수행 빈도를 계산할 필요가 있다. 다음 [보기]의 x←x+y의 수행 빈도수는?
[보기]
for i←1 to n do
for j←1 to n do
x←x+y
end
end
1) n
2) m
3) i*j
4) n
2
알고리즘을 분석하기 위하여
측정할 내용
과 관계가 먼 것은?
1) 정확성(correctness)
2) 적합성(optimality)
3) 소요 공간(amount of space)
4) 중복성(debugging)
알고리즘의
점근(asymptotic) 성능
이란?
1) 알고리즘이 정확히 몇 개의 명령문을 수행하는지를 나타낸 것
2) 알고리즘의 해가 얼마만큼의 오차를 포함하는지를 나타낸 것
3) 근사해를 구하는 데 필요한 알고리즘의 수행시간과 공간
4) 입력의 크기 n이 커질 때 알고리즘의 성능이 어떤 항에 좌우되는가를 나타낸 것
다음은 알고리즘 계산시간이다.
n이 매우 클 때의 관계식
으로 맞는 것은?
1) O(1) < O(logn) < O(n) < O(n
2
)
2) O(nlogn) < O(logn) < O(2
n
) < O(n
2
)
3) O(nlogn) < O(1) < O(n) < O(n
2
)
4) O(nlogn) < O(logn) < O(n) < O(n
2
)
