Tôi quan tâm đến độ phức tạp tiệm cận (lớn O) của hoạt động GroupBy trên các tập dữ liệu chưa được lập chỉ mục. Sự phức tạp của thuật toán được biết đến nhiều nhất và độ phức tạp của thuật toán mà các máy chủ SQL và LINQ đang sử dụng là gì?Sự phức tạp tiệm cận của hoạt động GroupBy là gì?
Bỏ qua SQL cơ sở mà nhóm đang hoạt động, khi được trình bày cho hoạt động GROUP BY, độ phức tạp chỉ là O (n) vì dữ liệu được quét mỗi hàng và được tổng hợp trong một lần truyền. Nó chia tuyến tính thành n (kích thước của tập dữ liệu).
Khi nhóm theo được thêm vào truy vấn phức tạp, phương trình thay đổi, O (n) trở thành giới hạn trên mà nhóm theo thêm vào phương trình tổng thể; nó có thể ít hơn nếu truy vấn phức tạp bên trong là như vậy mà trong độ phân giải của truy vấn cơ sở, dữ liệu đã được sắp xếp.
Và vì không có chỉ mục, khi dữ liệu được sắp xếp, bạn đã dùng O (N log N) để sắp xếp nó. (nitpick: nó tỷ lệ tuyến tính thành n, tức là kích thước của tập dữ liệu, không phải kích thước của n) –
@Martinho - Tôi đã sửa lỗi cú pháp tiếng Anh .. – RichardTheKiwi
Xin lỗi nhưng điều này là sai. Khi bạn đang lặp qua bộ dữ liệu, bạn phải quyết định nhóm nào bạn muốn đặt trong hàng/đối tượng đã cho. Tôi không thể thấy làm thế nào có thể được lựa chọn nhóm thực hiện trong thời gian không đổi. –
Giới thiệu về Linq, tôi đoán bạn muốn biết về nhóm LINQ-to-object theo độ phức tạp (Enumerable.GroupBy).
Kiểm tra việc triển khai với ILSpy, có vẻ như đó là O (n). (.Net Framework 4 series.)
Nó liệt kê tuyển tập nguồn một lần. Đối với mỗi phần tử, nó tính toán khóa nhóm của nó. Sau đó, nó sẽ kiểm tra nếu nó đã có chìa khóa trong một bản đồ có thể bắt đầu với các danh sách các phần tử, thêm khóa vào hashtable nếu nó bị thiếu. Sau đó, nó thêm phần tử vào danh sách mục nhập tương ứng trong Hashtable.
Lưu ý rằng GroupBy trong SQL và LINQ là hai hoạt động rất khác nhau. –