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 của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΩ (Big Omega)
2. BO (Big O)
3. Co (little o)
4. DΘ (Big Theta)

Độ 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)
2. BO(1)
3. CO(n log n)
4. DO(n²)

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ALogarit luôn được làm tròn thành số nguyên
2. BCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
3. CCơ số chỉ quan trọng với n nhỏ
4. DMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

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(log n)
2. BO(n)
3. CO(n²)
4. DO(n log n)

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

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

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

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