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

알고리즘의 실행 시간이 O(n)입니다. 이 증가를 무엇이라고 합니까?

1. A상수
2. B로그
3. C선형
4. D이차

루프가 i = 1에서 시작하여 i > n이 될 때까지 매 반복마다 i를 두 배로 합니다. 몇 번 반복합니까?

1. A약 n²
2. B약 log₂ n
3. C약 n / 2
4. D약 n

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

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

최악의 경우 비교 기반 정렬의 하한은 무엇입니까?

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

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

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

표준 삼중 루프로 두 n × n 행렬을 곱하는 시간 복잡도는 무엇입니까?

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

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

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

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

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