DAA-Test L2

Độ phức tạp thời gian của thuật toán được biểu diễn như thế nào?

• Một hằng số

• Một biến

• Một hàm của kích thước dữ liệu vào

• Một giá trị đo được

Answer explanation

Độ phức tạp thời gian mô tả sự tăng trưởng của thời gian thực hiện thuật toán khi kích thước dữ liệu đầu vào tăng lên. Nó được biểu diễn bằng một hàm toán học, thường là hàm của biến n (kích thước dữ liệu vào).

Đánh giá thời gian thực hiện thuật toán bằng phương pháp thực nghiệm là gì?

• Phân tích code để tìm ra độ phức tạp

• Chạy thuật toán với dữ liệu khác nhau và đo thời gian

• Sử dụng các công cụ toán học để ước tính thời gian

• Dự đoán thời gian chạy dựa trên kinh nghiệm

Answer explanation

Đánh giá thực nghiệm là chạy thuật toán trên máy tính với các bộ dữ liệu khác nhau và đo thời gian thực hiện. Phương pháp này cho kết quả trực quan, nhưng phụ thuộc vào phần cứng và dữ liệu thử nghiệm.

Chứng minh tính đúng của thuật toán là gì?

• Chạy thử thuật toán với nhiều dữ liệu

• Kiểm tra kết quả của thuật toán

• Chứng minh bằng lý luận logic rằng thuật toán luôn cho kết quả đúng

• So sánh thuật toán với các thuật toán khác

Answer explanation

Chứng minh tính đúng đắn là quá trình sử dụng các phương pháp toán học và logic để chứng minh rằng thuật toán sẽ luôn hoạt động đúng như mong đợi, bất kể dữ liệu đầu vào là gì.

Phương pháp nào thường được sử dụng để chứng minh tính đúng của thuật toán lặp?

• Phản chứng

• Trực giác

• Quy nạp

• Bất biến vòng lặp

Answer explanation

Bất biến vòng lặp là một mệnh đề đúng trước, trong và sau mỗi lần lặp của vòng lặp. Bằng cách chứng minh bất biến đúng và kết hợp với điều kiện dừng của vòng lặp, ta có thể chứng minh tính đúng của thuật toán lặp.

Thuật toán có độ phức tạp O(n²) sẽ mất bao lâu để xử lý dữ liệu gấp đôi kích thước?

• Gấp đôi thời gian

• Gấp đôi thời gian

• Gấp bốn thời gian

• Không thay đổi

Answer explanation

Kích thước dữ liệu vào ảnh hưởng tới hàm đánh giá độ phức tạp theo bậc của hàm.

Để chứng minh tính đúng của một thuật toán, ta cần chỉ ra:

• Thuật toán luôn nhanh hơn các thuật toán khác

• Thuật toán trả về kết quả đúng cho mọi đầu vào hợp lệ

• Thuật toán chắc chắn dừng

• Thuật toán sử dụng ít bộ nhớ nhất

Answer explanation

Chứng minh tính đúng của thuật toán là sử dụng các kĩ thuật phù hợp để chỉ ra rằng thuật toán sẽ cho ra kết quả đúng với mọi dữ liệu đầu vào.

Thuật toán đệ quy là gì?

• Một thuật toán gọi chính nó với đầu vào nhỏ hơn

• Một thuật toán không bao giờ lặp lại

• Một thuật toán sử dụng vòng lặp thay vì hàm

• Một thuật toán chỉ hoạt động với đầu vào cố định

Answer explanation

Bài toán đệ quy là bài toán có lời giải được xác định thông qua lời giải của bài toán tương tự chính nó, nhưng với bộ tham số "đơn giản" hơn. Thuật toán đệ quy giải bài toán đệ quy nên có lời gọi tới chính thuật toán đó với tham số đầu vào nhỏ hơn, đơn giản hơn.

Để chứng minh tính đúng của một thuật toán đệ quy, ta cần chứng minh điều gì?

• Thuật toán chạy nhanh hơn vòng lặp

• Trường hợp suy biến đúng và mỗi lần gọi đệ quy đều tiến gần đến trường hợp suy biến

• Thuật toán không bao giờ vượt quá bộ nhớ

• Thuật toán chỉ gọi chính nó một lần

Answer explanation

Thuật toán đệ quy đúng khi trường hợp suy biến đúng và mỗi lời gọi đệ quy các tham số sẽ dần tiến đến trường hợp suy biến đã có lời giải

Nếu f(n) = log n và g(n) = √n, mối quan hệ tốc độ tăng trưởng nào đúng?

• f(n) = O(g(n))

• g(n) = O(f(n))

• f(n) = Θ(g(n))

• f(n) tăng nhanh hơn g(n)

Answer explanation

log n tăng chậm hơn √n, nên f(n) = O(g(n)).

Hàm nào tăng trưởng chậm nhất trong các hàm sau?

• log (log n)

• log n

• √n

• n

Answer explanation

log (log n) tăng cực kỳ chậm so với các hàm còn lại.