Gợi ý phân tích thuật toán chương trình Lisp?

Question

Các hoạt động nào trong các chương trình Lisp thường được coi là nguyên thủy đầy đủ để tính cho một "bước" trong phân tích thuật toán? Làm thế nào rộng rãi để hiện đại lisps khác nhau trong việc thực hiện của họ?

Chắc chắn số học với số nguyên nhỏ sẽ được tính là một bước duy nhất, nhưng số lượng lớn hơn thì sao? Và những gì về việc xem xét sự khác biệt giữa reverse và nreverse? Cụ thể, là nreverse theta của reverse? Điều gì về tất cả các hoạt động mảng và chuỗi? Ngoài ra, làm thế nào để macro hình trong - làm thế nào tôi nên suy nghĩ về các macro khi phân tích phức tạp?

Answer 1

• Đừng cố gắng tìm một lớp dưới cùng của "bước đơn nhất" đồng nhất, chỉ cần biết O (1) là gì và không có gì.
• Việc thêm "số lớn hơn" (bignum s) phải là O (log n) trong đó n là lớn hơn của các số nguyên. Có nhiều thuật toán khác nhau cho phép nhân; Tôi không phải là một chuyên gia trong lĩnh vực này, và điều này có thể được thực hiện cụ thể.
• reverse và nreverse cả hai có thể được triển khai O (n) (reverse bằng chiến lược đầu ra cdr-đầu vào và khuyết điểm-đầu ra; nreverse bằng cách trao đổi con trỏ trong khi cdring). Nếu tôi hiểu thuật ngữ lạ "theta của" một cách chính xác, thì có. Tuy nhiên, lưu ý rằng tiêu chuẩn CL không đảm bảo về độ phức tạp của thời gian.
• Hoạt động chuỗi được cài đặt sẵn thường được thực hiện bằng cách chọn triển khai thực hiện theo danh sách hoặc danh sách tùy thuộc vào loại đối số, và do đó được mong đợi là thuật toán hiệu quả thông thường cho loại dữ liệu đó.
• Macro chỉ mở rộng sang mã khác. Bạn có thể xem xét việc mở rộng của họ, hoặc xem những gì họ đang làm tài liệu để làm, hoặc làm cho một đoán về giáo dục về các thuật toán mở rộng của họ sử dụng. Sự phức tạp của macroexpander là hoàn toàn không liên quan (trừ khi bạn đang sử dụng eval/compile, trong trường hợp này bạn cũng phải suy nghĩ về sự phức tạp của trình biên dịch thực hiện) vì nó chạy ở thời gian biên dịch, một lần; chỉ các mã mở rộng quan trọng.