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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Thời gian chạy nào sau đây là đa thức?

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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. AHằng số
2. BLogarit
3. CTuyến tính
4. DBậc hai

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng n / 2
2. BKhoảng log₂ n
3. CKhoảng n
4. DKhoảng √n

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

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

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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

Phát biểu nào về P và NP là đúng?

1. ANP có nghĩa là "không đa thức"
2. BMọi bài toán trong P cũng thuộc NP
3. CĐã được chứng minh rằng P ≠ NP
4. DCác bài toán NP không thể được kiểm chứng nhanh