BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA THỜI GIAN THUẬT TOÁN

Câu 1: Cho đoạn thông tin:

Trong lập trình, độ phức tạp thời gian của thuật toán được sử dụng để dự đoán số bước thực hiện của chương trình theo kích thước đầu vào. Độ phức tạp thời gian thường được biểu diễn bằng ký hiệu Big O (O(n), O(log n), O(n^2),...). Việc phân tích độ phức tạp giúp lập trình viên chọn lựa thuật toán phù hợp cho bài toán cụ thể.

Hãy đánh giá tính đúng sai của các nhận định sau:

a) Độ phức tạp thời gian không có ảnh hưởng đến hiệu suất của chương trình.
b) Ký hiệu Big O giúp mô tả tốc độ tăng trưởng của thuật toán.
c) Phân tích độ phức tạp thời gian chỉ cần thiết cho các chương trình nhỏ.
d) Độ phức tạp O(n^2) thường chậm hơn O(n) khi kích thước đầu vào lớn.

Câu 2: Cho đoạn thông tin:

Quy tắc cộng trong phân tích độ phức tạp thời gian cho biết rằng nếu một thuật toán bao gồm nhiều phần, thời gian thực hiện tổng thể sẽ là tổng thời gian thực hiện của từng phần. Điều này có nghĩa là nếu một phần có độ phức tạp O(n) và một phần khác có độ phức tạp O(m), thì tổng độ phức tạp sẽ là O(n + m).
Hãy đánh giá tính đúng sai của các nhận định sau:

a) Quy tắc cộng chỉ áp dụng cho các thuật toán có độ phức tạp giống nhau.
b) Nếu một thuật toán có độ phức tạp O(n) và O(m), tổng độ phức tạp sẽ là O(n * m).
c) Quy tắc cộng giúp tính toán thời gian thực hiện cho các thuật toán phức tạp.
d) Tổng độ phức tạp của một thuật toán là tổng của các độ phức tạp riêng biệt.

Câu 3: Cho đoạn thông tin:

Độ phức tạp thời gian O(log n) thường được thấy trong các thuật toán tìm kiếm nhị phân, nơi mà kích thước dữ liệu được chia đôi trong mỗi bước. Điều này cho phép tìm kiếm một phần tử trong danh sách đã sắp xếp một cách nhanh chóng.
Hãy đánh giá tính đúng sai của các nhận định sau:

a) Tìm kiếm nhị phân chỉ có thể được sử dụng trên các danh sách chưa sắp xếp.
b) Độ phức tạp O(log n) là rất hiệu quả cho việc tìm kiếm trong danh sách lớn.
c) Tìm kiếm nhị phân có thể thực hiện trong O(n) thời gian.
d) Danh sách phải được sắp xếp trước khi áp dụng thuật toán tìm kiếm nhị phân.

Câu 4: Cho đoạn thông tin:

Quy tắc nhân trong phân tích độ phức tạp thời gian cho biết rằng nếu một thuật toán gồm nhiều vòng lặp lồng nhau, độ phức tạp thời gian sẽ là tích của độ phức tạp của từng vòng lặp. Ví dụ, nếu có hai vòng lặp lồng nhau, mỗi vòng lặp có độ phức tạp O(n), thì tổng độ phức tạp sẽ là O(n^2).
Hãy đánh giá tính đúng sai của các nhận định sau:

a) Quy tắc nhân không áp dụng cho các thuật toán có vòng lặp.
b) Độ phức tạp O(n^2) có thể xảy ra trong các thuật toán có vòng lặp lồng nhau.
c) Quy tắc nhân chỉ áp dụng cho các thuật toán phân chia.
d) Nếu một thuật toán có ba vòng lặp lồng nhau, độ phức tạp có thể là O(n^3).

Câu 5: Cho đoạn thông tin:

Trong Python, việc sử dụng các cấu trúc dữ liệu như danh sách, tập hợp, và từ điển cũng ảnh hưởng đến độ phức tạp thời gian của thuật toán. Ví dụ, việc truy cập một phần tử trong danh sách có độ phức tạp O(1), trong khi truy cập một phần tử trong từ điển cũng có độ phức tạp O(1) nhưng việc tìm kiếm trong danh sách chưa sắp xếp có thể mất O(n) thời gian.
Hãy đánh giá tính đúng sai của các nhận định sau:

a) Tất cả các cấu trúc dữ liệu trong Python đều có độ phức tạp truy cập giống nhau.
b) Truy cập một phần tử trong từ điển là O(1).
c) Danh sách luôn có độ phức tạp O(1) cho mọi thao tác.
d) Việc sử dụng đúng cấu trúc dữ liệu có thể cải thiện hiệu suất của chương trình.