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

표준 배열 기반 병합 정렬은 추가 메모리를 얼마나 사용합니까?

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

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

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

log₂ 1024는 얼마입니까?

1. A10
2. B512
3. C32
4. D12

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

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

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

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

간선 가중치가 음이 아닌 그래프에서 하나의 출발점으로부터 최단 경로를 찾는 알고리즘은 무엇입니까?

1. AKruskal 알고리즘
2. B모든 경우에 Bellman–Ford가 필요함
3. C깊이 우선 탐색(DFS)
4. DDijkstra 알고리즘

헬드-카프 동적 계획법 알고리즘은 외판원 문제를 정확히 풉니다. 도시가 n개일 때 실행 시간은 얼마입니까?

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

정점 V개, 간선 E개인 그래프에서 이진 힙을 사용한 다익스트라 알고리즘의 실행 시간은 얼마입니까?

1. AO(V × E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V + E)