10
Giả sử chúng ta đang duyệt qua biểu đồ và muốn xác định nhanh xem liệu nút có được nhìn thấy trước đó hay không. Chúng tôi có một vài điều kiện tiên quyết.Tra cứu phần tử nhanh cho một ngôn ngữ chức năng (Haskell)
- Nodes đã được đánh dấu với số nguyên giá trị 1..N
- Graph được thực hiện với các nút có một danh sách kề
- Mỗi giá trị số nguyên từ 1..N xảy ra trong đồ thị dưới, đó là kích thước N
Bất kỳ ý tưởng nào để thực hiện điều này theo cách hoàn toàn có chức năng? (Không cho phép bảng hoặc mảng băm).
Tôi muốn có cấu trúc dữ liệu có hai hàm hoạt động trên đó; thêm (thêm một số nguyên gặp phải) và tra cứu (kiểm tra nếu số nguyên đã được thêm). Cả hai tốt nhất nên dùng thời gian O (n) khấu hao cho N lần lặp lại.
Điều này có khả thi không?
Tôi giả định Data.Set sẽ cho hiệu suất logarit hoặc bán không đổi-thời gian trên addToSet và thành viên, trái ngược với hiệu năng thời gian cố định dự kiến với bảng băm? –
Chris, bạn nói đúng. Data.Set chèn và tra cứu hoạt động là O (log n). – namin
Nếu số nguyên của bạn đủ nhỏ cho loại Int, bạn có thể sử dụng Data.IntSet, phiên bản được tối ưu hóa của Set. – mattiast