logo

Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(n)

Cùng Toploigiai Trả lời câu hỏi trang 149 (Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(n)) Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng SGK Tin 11 Cánh Diều.

Câu hỏi: Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(n)

phép toán danh sách liên kết

Trả lời ngắn gọn: 

Các phép toán danh sách liên kết có thời gian thực hiện O(n) bao gồm phép toán tìm kiếm một nút, thêm một nút vào cuối danh sách, xoá một nút từ cuối danh sách, chèn một nút vào trước hoặc sau một nút cho trước và xoá một nút bất kỳ trong danh sách.

Trả lời chi tiết:

Các phép toán danh sách liên kết có thời gian thực hiện O(n) bao gồm:

- Tìm kiếm một phần tử: Để tìm kiếm một phần tử trong danh sách liên kết, ta phải duyệt qua từng nút của danh sách một cách tuần tự để tìm kiếm phần tử cần tìm. Thời gian thực hiện của phép toán này là O(n).

- Chèn một phần tử vào cuối danh sách: Để chèn một phần tử vào cuối danh sách, ta phải duyệt qua từng nút của danh sách để đến cuối danh sách và thực hiện thêm phần tử vào cuối danh sách. Thời gian thực hiện của phép toán này cũng là O(n).

- Xóa một phần tử khỏi danh sách: Để xóa một phần tử khỏi danh sách, ta phải tìm kiếm phần tử đó trong danh sách, sau đó thực hiện xóa phần tử đó bằng cách điều chỉnh các liên kết giữa các nút trong danh sách. Tương tự như tìm kiếm một phần tử, thời gian thực hiện của phép toán này là O(n).

- Đảo ngược danh sách: Để đảo ngược danh sách, ta phải duyệt qua từng nút của danh sách, thay đổi liên kết giữa các nút để đảo ngược danh sách. Vì vậy, thời gian thực hiện của phép toán này là O(n).

Xem toàn bộ: Soạn Tin 11 Cánh diều

icon-date
Xuất bản : 27/02/2023 - Cập nhật : 10/04/2023
/* */ /* */
/*
*/