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

다음 실행 시간 중 다항 시간은 무엇입니까?

1. AO(2ⁿ)
2. BO(n³)
3. CO(nⁿ)
4. DO(n!)

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

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

f(n) = Θ(g(n))은 무엇을 의미합니까?

1. Af는 g와 같은 비율로 증가하며, 위아래로 g의 상수배에 의해 한정된다
2. Bf는 g보다 엄격히 빠르게 증가한다
3. Cf는 g보다 엄격히 느리게 증가한다
4. D모든 n에 대해 f가 항상 g보다 작으므로, g가 위에서는 한정하지만 아래에서는 한정하지 않는다

가득 차면 용량을 두 배로 늘리는 동적 배열에 원소를 추가하는 연산의 분할 상환(amortised) 시간 복잡도는 무엇입니까?

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

함수가 n번 반복하는 루프 하나를 실행한 뒤, 따로 n번 반복하는 또 다른 루프를 실행합니다. 시간 복잡도는 무엇입니까?

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

도달 가능한 기저 사례가 없는 재귀 함수에 대한 진술 중 옳은 것은 무엇입니까?

1. AO(1) 시간에 실행된다
2. B호출 스택이 넘칠 때까지 계속 자신을 호출한다
3. C컴파일러가 항상 안전하게 끝나는 루프로 바꾼다
4. D자동으로 0을 반환한다

위상 정렬은 어떤 그래프에서만 가능합니까?

1. A방향성 비순환 그래프(DAG)
2. B완전 그래프
3. C음의 가중치를 가진 그래프
4. D무방향 그래프

어떤 문제가 NP-완전(NP-complete)이려면 어떤 조건을 만족해야 합니까?

1. A푸는 것이 불가능하다
2. BNP 밖에 있으면서 정지 문제처럼 모든 NP 문제보다 어렵다
3. CNP에 속하고 모든 NP 문제가 다항 시간에 그 문제로 환원된다
4. D다항 시간에 풀 수 있다