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

삽입 정렬(insertion sort)의 최악의 경우 시간 복잡도는 무엇입니까?

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

3n² + 5n + 2의 Big O는 무엇입니까?

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

O(2ⁿ) 증가를 무엇이라고 합니까?

1. A선형
2. B다항
3. C지수
4. D로그

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

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

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

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

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

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

동적 프로그래밍으로 푸는 0/1 배낭 문제는 O(nW) 시간이 걸립니다. 이것을 의사 다항 시간(pseudo-polynomial)이라고 부르는 이유는 무엇입니까?

1. A알고리즘이 무작위화되어 있어 입력마다 실행 시간이 달라지기 때문이다
2. Bn이 항상 작기 때문이다
3. CW = 0일 때만 작동하기 때문이다
4. DW는 수이므로 실행 시간이 W를 쓰는 데 쓰이는 비트 수에 대해 지수적이다

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

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