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

정렬된 배열에서 이진 탐색(binary search)의 시간 복잡도는 무엇입니까?

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

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

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

피벗을 골라 배열을 더 작은 원소와 더 큰 원소로 분할하는 정렬 알고리즘은 무엇입니까?

1. A삽입 정렬
2. B퀵 정렬
3. C버블 정렬
4. D병합 정렬

점화식 T(n) = 2T(n/2) + O(1)의 해는 무엇입니까?

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

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

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

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

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

결정 문제 X가 NP-complete임을 증명하려면 어떤 두 가지를 보여야 합니까?

1. AX가 P에 속하는 문제로 환원되고, X가 NP에 속한다
2. BX가 NP에 속하고, 알려진 NP-complete 문제가 다항 시간에 X로 환원된다
3. CX가 P에 속하고, X가 SAT로 환원된다
4. DX에 다항 알고리즘이 없고, X가 결정 가능하다

해시 테이블의 평균 조회 시간은 O(1)인데 최악의 경우는 O(n)인 이유는 무엇입니까?

1. A많은 키가 같은 버킷에서 충돌(collision)할 수 있기 때문이다
2. B해시 함수가 느리기 때문이다
3. C배열 접근이 O(n)이기 때문이다
4. D키를 먼저 정렬해야 하기 때문이다