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

표준 배열 기반 병합 정렬은 추가 메모리를 얼마나 사용합니까?

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

알고리즘의 최악의 경우 실행 시간은 무엇을 나타냅니까?

1. A느린 컴퓨터에서 걸리는 시간
2. B크기 n인 무작위 입력에서 걸리는 기대 시간
3. C크기 n인 모든 입력 중에서 걸리는 최대 시간
4. D가장 작은 입력에서 걸리는 시간

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

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

문제가 최적 부분 구조를 가진다는 것은 무엇을 의미합니까?

1. A최적해를 부분 문제들의 최적해로부터 만들 수 있다
2. B문제를 상수 시간에 풀 수 있다
3. C문제의 최적해가 정확히 하나이며 모든 부분 문제가 그것을 공유한다
4. D모든 부분 문제의 크기가 같다

for i = 1 to n: for j = 1 to i: O(1) 작업 수행 — 이 코드의 시간 복잡도는 무엇입니까?

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

정렬된 배열에서 양 끝에서 포인터를 하나씩 안쪽으로 움직이며 합이 목표값인 두 원소를 찾습니다. 시간 복잡도는 무엇입니까?

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

결정 불가능한 문제와 다루기 어려운 문제의 차이는 무엇입니까?

1. A다루기 어려운 문제는 어떤 알고리즘으로도 풀 수 없고, 결정 불가능한 문제는 지수 시간만 있으면 된다
2. B결정 불가능한 문제는 NP에, 다루기 어려운 문제는 P에 속한다
3. C결정 불가능한 문제는 모든 입력에 대한 알고리즘이 없고, 다루기 어려운 문제는 알고리즘이 있지만 너무 느리다
4. D둘 다 그 문제에 알고리즘이 전혀 없다는 뜻이다

다음 충족 가능성 문제 중 다항 시간에 풀 수 있다고 알려진 것은 무엇입니까?

1. A회로 충족 가능성
2. B각 절에 리터럴이 최대 두 개인 2-SAT
3. C각 절에 리터럴이 정확히 세 개인 3-SAT
4. D논리곱 표준형 식에 대한 일반 SAT