Tại sao thao tác xóa và chèn trong linked list có độ phức tạp O(1)?
Tại sao thao tác xóa và chèn trong linked list có độ phức tạp O(1)?
Chèn/ xoá chỉ cần đổi vài con trỏ, không dịch phần tử:
# chèn node mới sau nút p
new.next = p.next
p.next = new
# xoá nút sau p
p.next = p.next.next
Số bước cố định ⇒ O(1) — với điều kiện đã có con trỏ tới vị trí. Nếu phải tìm vị trí theo giá trị/ chỉ số thì tổng là O(n). So với mảng: chèn giữa phải dịch O(n) phần tử.
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.