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

문제가 보통 다루기 쉽다(tractable)고 불리는 것은 언제입니까?

1. A상수 시간에 풀 수 있을 때
2. B해가 없을 때
3. C다항 시간에 풀 수 있을 때
4. D모든 가능성을 시도해야만 풀 수 있을 때

이미 정렬된 배열에서 삽입 정렬의 최선의 경우 시간 복잡도는 무엇입니까?

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

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

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

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

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

정렬된 배열에서 양 끝에서 포인터를 하나씩 안쪽으로 움직이며 합이 목표값인 두 원소를 찾습니다. 시간 복잡도는 무엇입니까?

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

활동 선택 문제에서 겹치지 않는 활동의 수를 항상 최대로 만드는 탐욕적 규칙은 무엇입니까?

1. A가장 일찍 시작하는 활동을 고른다
2. B겹침이 가장 적은 활동을 먼저 고른 뒤, 호환되는 활동들로 반복한다
3. C가장 일찍 끝나는 활동을 고르고, 호환되는 활동들로 반복한다
4. D가장 짧은 활동을 먼저 고른다

마스터 정리를 사용하면 T(n) = 8T(n/2) + O(n²)의 해는 무엇입니까?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n² log n)

정지 문제(halting problem)가 보여 주는 것은 무엇입니까?

1. A일부 프로그램은 더 빠른 컴퓨터에서 더 빨리 실행되므로 정지 여부는 하드웨어에 달려 있다
2. B루프는 피해야 한다
3. C모든 프로그램은 결국 정지한다
4. D모든 프로그램과 입력에 대해 그것이 정지하는지를 판정할 수 있는 알고리즘은 없다