2008-10-07 8 views

Trả lời

8

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.

+0

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

2

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.

6

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.

2

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.