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

인접 리스트로 저장된 그래프에서 깊이 우선 탐색(DFS)의 시간 복잡도는 무엇입니까?

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

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

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

O(2ⁿ) 증가를 무엇이라고 합니까?

1. A선형
2. B로그
3. C지수
4. D다항

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

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

많은 라이브러리 정렬 루틴이 아주 작은 부분 배열에서 삽입 정렬로 전환하는 이유는 무엇입니까?

1. A재귀 알고리즘은 원소가 10개 미만인 배열을 처리하지 못하기 때문에
2. B삽입 정렬은 오버헤드가 적고 작거나 거의 정렬된 입력에서 빠르기 때문에
3. C삽입 정렬은 최악의 경우 O(n log n)이기 때문에
4. D큰 입력에서 삽입 정렬이 다른 어떤 정렬 알고리즘보다 메모리를 적게 쓰기 때문에

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

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

클래스 NP의 올바른 정의는 무엇입니까?

1. A어떤 알고리즘으로도 풀 수 없는 문제
2. B다항 시간에 풀 수 없는 문제
3. C다항이 아닌 문제
4. D인증서가 주어지면 "예" 답을 다항 시간에 검증할 수 있는 결정 문제

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

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