Thời gian chạy của thủ tục nối thêm O (n)?

Question

Ví dụ: trong OCaml khi bạn thêm một mục vào danh sách độ dài n.

x@[mylist] 

Answer 1

Vâng, thời gian chạy của @ trong OCaml là O(n) (nơi n là chiều dài của toán hạng bên trái).

Thường bổ sung vào cuối danh sách được liên kết đơn lẻ không thay đổi (hoặc danh sách được liên kết đôi không thay đổi cho vấn đề đó) sẽ luôn là O(n).

Answer 2

Tóm lại, có.

Để minh họa, một đơn giản chức năng (không đuôi-đệ quy) thêm có thể được viết như sau:

let rec (@) xs ys = 
    match xs with 
    | [] -> ys 
    | x::xs' -> x::(xs' @ ys) 

Vì vậy, trong nội bộ append (@) bị phá vỡ danh sách đầu tiên (xs) và sử dụng cons (::) nhà điều hành để xây dựng danh sách kết quả. Thật dễ dàng để thấy rằng có ba bước chuẩn bị trước (::), trong đó n là độ dài của danh sách đầu tiên.

Answer 3

Vâng, như đã đề cập, có hai lý do tại sao nó phải là O (n):

1. Bạn phải lặp đến cuối danh sách đơn lẻ liên kết, trong đó có O (n)

2. Kể từ khi cặp là không thay đổi, bạn phải sao chép tất cả các cặp trong danh sách đầu tiên để nối thêm, mà cũng phải mất O (n)

Một chủ đề thú vị liên quan là đuôi-đệ quy vs đệ quy không đuôi wa ys để thêm

Answer 4

Đoạn mã của bạn không khớp với câu hỏi của bạn, điều này gợi ý bạn nhầm lẫn về những gì nhà điều hành làm hoặc nhà điều hành nào sử dụng.

Nhà cung cấp @ hoặc List.append nối 2 danh sách và list1 @ list2 mất thời gian O (length (list1)) và không phải đệ quy đuôi. rev_append là đệ quy đuôi nhưng vẫn O (n) trong thời gian. Cách thông thường để thêm một mục vào danh sách tuy nhiên là với hàm tạo :: và item :: mylist mất O (1) lần.