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

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

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

각각 n번 실행되는 두 개의 중첩 루프를 가진 알고리즘은 일반적으로 어떤 복잡도를 가집니까?

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

O(n) 알고리즘이 n = 100만에서 3초 걸립니다. n = 200만에서는 대략 얼마나 걸립니까?

1. A9초
2. B3초
3. C12초
4. D6초

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

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

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

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

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

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

일부 간선 가중치가 음수일 때 다익스트라 알고리즘이 틀린 결과를 줄 수 있는 이유는 무엇입니까?

1. A정점은 추출될 때 확정되지만, 나중의 음수 간선이 여전히 더 짧은 경로를 줄 수 있기 때문에
2. B음수 간선마다 무한 루프에 빠지기 때문에
3. C무방향 그래프에서만 동작하기 때문에
4. D우선순위 큐에 음수를 저장할 수 없기 때문에

위상 정렬은 어떤 그래프에서만 가능합니까?

1. A음의 가중치를 가진 그래프
2. B방향성 비순환 그래프(DAG)
3. C완전 그래프
4. D무방향 그래프