Có danh sách chủ của ký hiệu Big-O cho mọi thứ không? Cấu trúc dữ liệu, thuật toán, hoạt động được thực hiện trên từng trường hợp, trường hợp trung bình, trường hợp xấu nhất, v.v.Có danh sách tổng thể về ký hiệu Big-O cho mọi thứ không?
Trả lời
Dictionary of Algorithms and Data Structures là danh sách khá toàn diện và bao gồm độ phức tạp (Big-O) trong mô tả của thuật toán. Nếu bạn cần thêm thông tin, nó sẽ nằm trong một trong các tài liệu tham khảo được liên kết và luôn có Wikipedia như một dự phòng.
Hãy thử "Introduction to Algorithms" của Cormen, Leisersen và Rivest. Nếu nó không ở trong đó có lẽ nó không đáng biết.
Introduction to Algorithms, Second Edition, còn gọi là CLRS (Cormen, Leiserson, Rivest, Stein), là điều gần nhất tôi có thể nghĩ đến.
Nếu không thành công, hãy thử The Art of Computer Programming, bởi Knuth. Nếu nó không có trong đó, bạn có thể cần phải làm một số nghiên cứu thực sự.
Cormen book là nhiều hơn về cách dạy bạn cách chứng minh Big-O sẽ là gì cho một thuật toán nhất định, chứ không phải là ghi nhớ thuật toán cho hiệu suất Big-O của nó. Trước đây là có giá trị hơn nhiều so với thứ hai, và đòi hỏi một sự đầu tư về phía bạn.
Trong c + + các tiêu chuẩn STL được xác định bởi các đặc tính Big-O của các thuật toán cũng như các yêu cầu về không gian. Bằng cách đó bạn có thể chuyển đổi giữa các triển khai cạnh tranh của STL và vẫn biết rằng chương trình của bạn có các đặc tính thời gian chạy giống nhau. Việc triển khai STL đặc biệt tốt thậm chí có thể liệt kê các danh sách trường hợp đặc biệt của các loại cụ thể tốt hơn các yêu cầu tiêu chuẩn.
Giúp bạn dễ dàng chọn đúng loại vòng lặp hoặc danh sách cho một vấn đề cụ thể, vì bạn có thể dễ dàng cân nhắc giữa mức tiêu thụ không gian và tốc độ.
Ofcourse Big-O chỉ là dòng hướng dẫn vì tất cả các hằng số đều bị xóa. Nếu một thuật toán chạy trong k * O (n), nó sẽ được phân loại là O (n), nhưng nếu k là đủ cao nó có thể tồi tệ hơn O (n^2) đối với một số giá trị n và m.
Đối với bất kỳ ai đến với câu hỏi này từ Google.
Tôi đã tải xuống tất cả các trang và liệt kê tất cả các trang cung cấp lớn o: https://pastebin.com/X3c7i4aF – BlackCap