Tôi có nên xem xét memmove() O (n) hoặc O (1) không?

điều này có thể là một câu hỏi ngớ ngẩn, nhưng tôi muốn tính toán độ phức tạp của một trong các thuật toán của tôi và tôi không chắc chắn về độ phức tạp để xem xét cho hàm memmove().Tôi có nên xem xét memmove() O (n) hoặc O (1) không?

Bạn có thể vui lòng giúp/giải thích không?

void * memmove (void * destination, const void * source, size_t num);

Vì vậy, độ phức tạp là O (num) hoặc O (1). Tôi cho rằng đó là O (num), nhưng tôi không chắc chắn vì bây giờ tôi thiếu hiểu biết về những gì đang xảy ra dưới mui xe.

Nguồn

2010-04-25 Andrei Ciobanu

Câu trả lời đúng có thể là tùy thuộc vào việc triển khai thực hiện. Bạn có thể tưởng tượng một hệ thống bất thường nơi bộ nhớ thực sự là một số đồ thị phức tạp hoặc danh sách liên kết. Trong mọi hệ thống thực, tôi biết nó tỉ lệ với num. –

Vì thời gian chạy của memmove tăng tỷ lệ thuận với số byte cần thiết để di chuyển, đó là O (n).

Nguồn

2010-04-25 21:20:30

O (n) là độ phức tạp tiệm cận chính xác, nhưng tôi không nghĩ rằng tôi sẽ sử dụng thuật ngữ "tỷ lệ trực tiếp" trong ngữ cảnh này, ngay cả đối với một cái gì đó đơn giản như 'memmove'. Xem xét n = 4 so với n = 1 byte trên kiến trúc 32 bit: trường hợp n = 1 có thể thực sự là hoạt động đắt tiền hơn! –

Đó là 'O (n)' trong đó 'n' là số được chuyển đến' memmove() '- nhưng điều đó có thể không tỉ lệ với' n' mà bạn đang sử dụng để mô tả thuật toán của bạn. – caf

Bạn đang áp dụng hoạt động memmove() cho - các yếu tố được chọn trong thuật toán hoặc tất cả chúng? Bạn đang áp dụng memmove() cho các phần tử nhiều lần?

Đó là những điều quan trọng đối với độ phức tạp của thuật toán.

Câu trả lời có thể khác nhau mà sự phức tạp của memmove() bản thân về các mảng của char yếu tố mà memmove() giao dịch với (mà memmove() là O (n) hoạt động).

Nguồn

2010-04-26 07:57:32

Tôi có nên xem xét memmove() O (n) hoặc O (1) không?

Trả lời

Các vấn đề liên quan