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

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

1. AΩ (Big Omega)
2. BΘ (Big Theta)
3. Co (little o)
4. DO (Big O)

다음 실행 시간 중 다항 시간은 무엇입니까?

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

f(n) = Θ(g(n))은 무엇을 의미합니까?

1. A모든 n에 대해 f가 항상 g보다 작으므로, g가 위에서는 한정하지만 아래에서는 한정하지 않는다
2. Bf는 g보다 엄격히 느리게 증가한다
3. Cf는 g보다 엄격히 빠르게 증가한다
4. Df는 g와 같은 비율로 증가하며, 위아래로 g의 상수배에 의해 한정된다

for i = 1 to n: (j = 1; while j < n: j = j × 2) — 이 코드의 시간 복잡도는 무엇입니까?

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

프림 알고리즘은 최소 신장 트리를 어떻게 만듭니까?

1. A너비 우선 탐색을 실행하고 BFS 트리를 유지한다
2. B시작 정점에서 트리 하나를 키우며 트리를 떠나는 가장 싼 간선을 추가한다
3. C간선을 가중치순으로 모두 정렬하여 숲에서 사이클을 만들지 않는 간선을 하나씩 추가한다
4. D사이클이 없어질 때까지 가장 비싼 간선을 제거한다

상향식 표로 n번째 피보나치 수를 계산하는 시간 복잡도는 무엇입니까?

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

쿡-레빈 정리는 무엇을 확립했습니까?

1. AP는 NP와 같지 않다
2. B모든 NP 문제는 지수 시간에 풀 수 있다
3. C정지 문제는 결정 불가능하다
4. D불리언 충족 가능성 문제(SAT)는 NP-complete이다

벨만-포드 알고리즘은 출발점에서 도달 가능한 음의 가중치 사이클을 어떻게 탐지합니까?

1. A깊이 우선 탐색으로 사이클 수를 센다
2. BV − 1 라운드 후 아직 완화할 수 있는 간선이 있는지 확인한다
3. C다익스트라 알고리즘을 두 번 실행하여 두 거리 결과를 비교한다
4. D음의 가중치를 가진 간선이 있는지 확인한다