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

병합 정렬의 최악의 경우 시간 복잡도는 무엇입니까?

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

증가율의 상한(upper bound)을 나타내는 표기법은 무엇입니까?

1. ABig Omega
2. BBig Theta
3. CBig O
4. DLittle omega

n개의 수로 된 정렬되지 않은 배열에서 가장 큰 값을 찾는 시간 복잡도는 무엇입니까?

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

동적 계획법이 병합 정렬에 실질적인 속도 향상을 주지 못하는 이유는 무엇입니까?

1. A부분 문제가 겹치지 않아 재사용할 것이 없기 때문에
2. B병합 정렬은 이미 O(n)이기 때문에
3. C병합 정렬에는 재귀 구조가 없기 때문에
4. D동적 계획법은 배열이 아니라 그래프 문제에서만 동작하기 때문에

활동 선택 문제에서 겹치지 않는 활동의 수를 항상 최대로 만드는 탐욕적 규칙은 무엇입니까?

1. A가장 일찍 시작하는 활동을 고른다
2. B가장 짧은 활동을 먼저 고른다
3. C가장 일찍 끝나는 활동을 고르고, 호환되는 활동들로 반복한다
4. D겹침이 가장 적은 활동을 먼저 고른 뒤, 호환되는 활동들로 반복한다

퀵 정렬의 최악의 경우 시간 복잡도는 무엇입니까?

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

P와 NP에 대한 설명 중 옳은 것은 무엇입니까?

1. AP에 속하는 모든 문제는 NP에도 속한다
2. BNP 문제는 빠르게 검증할 수 없다
3. CP ≠ NP임이 증명되었다
4. DNP는 "not polynomial"을 의미한다

상향식(bottom-up) 방법으로 정렬되지 않은 n개의 원소로 이진 힙을 구성하는 시간 복잡도는 무엇입니까?

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