Bất cứ ai có thể chỉ cho tôi tài nguyên liệt kê sự phức tạp Big-O của các hàm thư viện clojure cơ bản như conj, cons, vv? Tôi biết rằng Big-O sẽ thay đổi tùy thuộc vào loại đầu vào, nhưng vẫn là một tài nguyên có sẵn? Tôi cảm thấy khó chịu khi viết một cái gì đó mà không có một ý tưởng thô sơ về việc nó sẽ chạy nhanh như thế nào.Big O của chức năng thư viện clojure
Dưới đây là một bảng sáng tác bởi John Jacobsen và đưa from this discussion:
muộn để đảng ở đây, nhưng tôi thấy the link in the comments of the first answer phải dứt khoát hơn, vì vậy tôi post lại nó ở đây với một vài sửa đổi (có nghĩa là, english->big-o):
Trên các bộ sưu tập chưa phân loại, O (log n) là thời gian gần như không đổi, và vì 2 các nút có thể vừa với các nút được phân đoạn bit trie, điều này có nghĩa là worst-case complexity of log32232 = 6.4. Vectơ cũng là tries where the indices are keys.
Bộ sưu tập được sắp xếp sử dụng tìm kiếm nhị phân nếu có thể. (Có, đây là cả hai kỹ thuật O (log n), bao gồm cả các yếu tố không đổi là để tham khảo.)
Danh sách đảm bảo thời gian không đổi cho hoạt động trên phần tử đầu tiên và O (n) cho mọi thứ khác.
Một "1" trong dấu ngoặc kép, là đủ gần với một đến không quan trọng (theo Rich Hickey.) Nhưng thực sự là O (log_32 chiều sâu)? –
Bảng này không hoàn toàn chính xác. 'last' luôn là O (n). 'cons' luôn là O (1) (giả sử' seq' luôn là O (1)). 'conj' trong một vector chỉ là" 1 ", không phải là 1. – kotarak
@ kotarak Bạn có thể xây dựng một chút về sửa chữa của bạn? :) – Anonymous