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

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

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

n이 클 때 가장 빠르게 증가하는 복잡도 클래스는 무엇입니까?

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

메모이제이션(memoisation)이란 무엇입니까?

1. A재귀를 동등한 루프로 자동 변환하여 호출 스택이 필요 없게 만드는 것
2. B함수 호출 결과를 저장하여 반복 호출에 메모리에서 답하는 것
3. C코드의 각 줄 옆에 주석을 쓰는 것
4. D함수가 반환된 뒤 메모리를 해제하는 것

원소가 1,000,000개인 정렬된 배열에서 이진 탐색은 최악의 경우 대략 몇 번 비교합니까?

1. A약 500,000
2. B약 1,000
3. C약 20
4. D약 100

플로이드-워셜 알고리즘은 무엇을 얼마나 빠르게 계산합니까?

1. A모든 정점 쌍 사이의 최단 경로를 O(V³)에
2. B위상 정렬 순서를 O(V²)에
3. C한 출발 정점에서 다른 모든 정점까지의 최단 경로를 O(V + E)에
4. D최소 신장 트리를 O(E log V)에

많은 라이브러리 정렬 루틴이 아주 작은 부분 배열에서 삽입 정렬로 전환하는 이유는 무엇입니까?

1. A삽입 정렬은 최악의 경우 O(n log n)이기 때문에
2. B큰 입력에서 삽입 정렬이 다른 어떤 정렬 알고리즘보다 메모리를 적게 쓰기 때문에
3. C삽입 정렬은 오버헤드가 적고 작거나 거의 정렬된 입력에서 빠르기 때문에
4. D재귀 알고리즘은 원소가 10개 미만인 배열을 처리하지 못하기 때문에

누군가 NP-complete 문제 하나에 대한 다항 시간 알고리즘을 찾는다면 어떤 결과가 따릅니까?

1. A그 문제 하나만 P로 옮겨진다
2. B모든 지수 시간 알고리즘이 즉시 선형 시간에 실행된다
3. CNP의 모든 문제를 다항 시간에 풀 수 있으므로 P = NP이다
4. D정지 문제가 결정 가능해진다

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

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