Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B10
3. C12
4. D512

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

Công thức truy hồi T(n) = T(n − 1) + O(n) có nghiệm là gì?

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Độ phức tạp thời gian của: for i = 1 to n: for (j = i; j ≤ n; j = j + i) thực hiện công việc O(1) là gì?

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

Cận nào là đúng cho log(n!)?

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