정답이 있는 알고리즘과 복잡도 학습지

평균적인 경우 실행 시간은 무엇을 나타냅니까?

1. A평균 길이 입력에 대한 시간
2. B가장 흔한 컴퓨터에서의 시간
3. C최선의 경우와 최악의 경우 실행 시간의 중간값
4. D크기 n인 입력의 주어진 분포에 대한 기대 시간

n개의 원소를 가진 정렬되지 않은 배열에서 선형 탐색(linear search)의 시간 복잡도(최악의 경우)는 무엇입니까?

1. AO(n²)
2. BO(n)
3. CO(1)
4. DO(log n)

각각 n번 실행되는 두 개의 중첩 루프를 가진 알고리즘은 일반적으로 어떤 복잡도를 가집니까?

1. AO(n)
2. BO(2n)
3. CO(n²)
4. DO(log n)

분할 상환 분석(amortised analysis)은 무엇을 측정합니까?

1. A최선의 입력에서 알고리즘의 비용
2. B무작위 입력에 대한 기대 비용
3. C최악의 연산 순서에 걸친 연산당 평균 비용
4. D연산열 전체에서 가장 비싼 단일 연산 하나의 비용

동적 프로그래밍(dynamic programming)은 문제가 무엇을 가질 때 유용합니까?

1. A중복되는 부분 문제와 최적 부분 구조
2. B부분 문제가 전혀 없어 한 단계로 풀 수 있음
3. C루프가 하나뿐임
4. D무작위 입력만 있음

정점 V개, 간선 E개인 그래프에서 벨만-포드 알고리즘의 시간 복잡도는 무엇입니까?

1. AO(V × E)
2. BO(E log V)
3. CO(V³ × E)
4. DO(V + E)

결정 문제 X가 NP-complete임을 증명하려면 어떤 두 가지를 보여야 합니까?

1. AX가 NP에 속하고, 알려진 NP-complete 문제가 다항 시간에 X로 환원된다
2. BX가 P에 속하고, X가 SAT로 환원된다
3. CX가 P에 속하는 문제로 환원되고, X가 NP에 속한다
4. DX에 다항 알고리즘이 없고, X가 결정 가능하다

마지막 두 값만 유지하는 루프로 n번째 피보나치 수를 계산할 때 시간과 공간 비용은 얼마입니까?

1. AO(log n) 시간과 O(n) 공간
2. BO(n) 시간과 O(1) 공간
3. CO(n) 시간과 O(n) 공간
4. DO(2ⁿ) 시간과 O(1) 공간