Tôi đang thiếu gì trong lý luận của mình?
Hai điều:
Có các chiến lược khác ngoài việc phân loại để tìm va chạm; một điều hiển nhiên là xây dựng một bảng băm khổng lồ. Bây giờ, trong thực tế, việc sắp xếp có thể sẽ diễn ra nhanh hơn (vì một bảng băm lớn như vậy sẽ không thực tế), nhưng về mặt lý thuyết, một bảng băm sẽ cho phép $O(1)$ truy cập mà phân tích phức tạp này giả định ngầm.
$O(n \log n)$ không thực sự là thời gian sắp xếp tối ưu. Đó là nếu các thao tác duy nhất bạn có thể thực hiện trên dữ liệu là so sánh và di chuyển dữ liệu; tuy nhiên chúng tôi không thực sự bị hạn chế theo cách đó. Một cách tiếp cận rõ ràng là thực hiện phương pháp sắp xếp cơ số, phương pháp này có thể có độ phức tạp về thời gian tốt hơn đáng kể.
Bây giờ, thành thật mà nói, chúng ta thường bỏ qua thời gian dành cho các hoạt động phi mã hóa này (chẳng hạn như tìm kiếm và sắp xếp), trừ khi chúng chiếm một phần rất lớn trong tổng thời gian. Thành thật mà nói, có thể có rất nhiều chi tiết khi bạn đi xuống cấp độ đó (chẳng hạn như sự phức tạp của việc xử lý $O(2^{56})$ dữ liệu), và thay vào đó chúng tôi chỉ tính các đánh giá DES.
Chúng tôi không thực sự cố gắng phá vỡ 2DES; thay vào đó, chúng tôi đang chứng minh rằng việc phá vỡ 2DES thực sự có thể đạt được trong thời gian thực tế. Nếu chúng tôi thực sự đang cố gắng phá vỡ nó, thay vào đó, chúng tôi có thể sử dụng tìm kiếm lambda, điều này sẽ có hệ số phức tạp tăng liên tục và không được đảm bảo, sẽ dễ triển khai hơn (vì tìm kiếm lambda sẽ sử dụng ít bộ nhớ hơn và vẫn dễ dàng song song hóa).
