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

무료 인쇄용 알고리즘과 복잡도 학습지: 쉬운 문제부터 시험 수준까지 8문제, 정답표 포함. 인쇄하거나 PDF로 저장하세요.

새 학습지힌트와 함께 온라인으로 연습하기

교수자 안내: 수업에서 무료로 인쇄, 복사, 사용할 수 있습니다. 새 워크시트마다 값이 새로 바뀌고 별도의 정답이 함께 제공됩니다. 강의 페이지에 ExamProblems 링크를 걸어 주시면 감사하겠습니다.

이름: ____________________   날짜: ____________

1.쉬움

n이 커질 때 다음 중 가장 느리게 증가하는 것은 무엇입니까?

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

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

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

증가율의 하한(lower bound)을 나타내는 표기법은 무엇입니까?

  1. AO (Big O)
  2. BΩ (Big Omega)
  3. CΘ (Big Theta)
  4. Do (little o)
4.보통

길이가 m과 n인 문자열의 최장 공통 부분 수열에 대한 표준 동적 계획법 알고리즘의 시간 복잡도는 무엇입니까?

  1. AO(mn log n)
  2. BO(2m+n)
  3. CO(mn)
  4. DO(m + n)
5.보통

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

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

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

  1. A약 20
  2. B약 100
  3. C약 500,000
  4. D약 1,000
7.어려움

마지막 두 값만 유지하는 루프로 n번째 피보나치 수를 계산할 때 시간과 공간 비용은 얼마입니까?

  1. AO(n) 시간과 O(1) 공간
  2. BO(n) 시간과 O(n) 공간
  3. CO(2ⁿ) 시간과 O(1) 공간
  4. DO(log n) 시간과 O(n) 공간
8.어려움

다음 충족 가능성 문제 중 다항 시간에 풀 수 있다고 알려진 것은 무엇입니까?

  1. A논리곱 표준형 식에 대한 일반 SAT
  2. B각 절에 리터럴이 정확히 세 개인 3-SAT
  3. C각 절에 리터럴이 최대 두 개인 2-SAT
  4. D회로 충족 가능성

정답표

  1. 1. D · O(log n)
  2. 2. B · O(2ⁿ)
  3. 3. B · Ω (Big Omega)
  4. 4. C · O(mn)
  5. 5. C · O(n²)
  6. 6. A · 약 20
  7. 7. A · O(n) 시간과 O(1) 공간
  8. 8. C · 각 절에 리터럴이 최대 두 개인 2-SAT

자세한 단계별 풀이: examproblems.com에서 이 주제를 연습하세요.