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

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

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

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

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

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

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

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

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

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

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

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

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

어떤 배낭 문제 변형에서 탐욕적 규칙 "무게당 가치 순으로 물건 담기"가 항상 최적의 답을 줍니까?

1. A물건을 통째로만 담아야 하는 0/1 배낭 문제
2. B두 변형 모두
3. C어느 변형도 아님
4. D물건을 나눌 수 있는 분할 가능 배낭 문제

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

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