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

알고리즘이란 무엇입니까?

1. A그래픽 인터페이스가 있는 모든 컴퓨터 프로그램
2. B문제를 해결하는 잘 정의된 단계들의 유한한 순서
3. C수를 저장하는 자료 구조
4. D수학 공식을 쓰기 위해 설계된 프로그래밍 언어

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

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

log₂ 1024는 얼마입니까?

1. A32
2. B512
3. C12
4. D10

동적 계획법이 병합 정렬에 실질적인 속도 향상을 주지 못하는 이유는 무엇입니까?

1. A병합 정렬에는 재귀 구조가 없기 때문에
2. B동적 계획법은 배열이 아니라 그래프 문제에서만 동작하기 때문에
3. C병합 정렬은 이미 O(n)이기 때문에
4. D부분 문제가 겹치지 않아 재사용할 것이 없기 때문에

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

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

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

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

슈트라센 알고리즘은 절반 크기 블록의 재귀 곱셈을 8번 대신 7번 사용하여 행렬을 곱합니다. 실행 시간은 얼마입니까?

1. AΘ(n³)
2. BΘ(n^{log₂ 7}), 약 n^2.81
3. CΘ(n²)
4. DΘ(n² log n)

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

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