Ma trận kề ngốn 1.527 MB ở V=40.000 và OOM quanh V~90.000, còn danh sách kề chỉ 2,6 MB. Bảng DP đầy đủ dùng 382 MB, bản cuộn hai biến dùng 1 MB cùng thời gian. Merge sort tốn gấp đôi RAM nhưng nhanh hơn heapsort 3,7 lần. Không gian là bức tường cứng, không phải tài nguyên miễn phí — tôi đọc VmHWM để đo.
Kẹp đồng hồ hai đầu vòng lặp rồi đọc số nghe đơn giản, nhưng con số ấy nói dối bốn kiểu: bỏ sink thì compiler xóa vòng và đo ra 0 ns cho việc chưa chạy; lần đầu chậm 27% vì cache lạnh; trên VM một lần vọt 2,7 lần median; và clock_gettime tốn 16 ns nên đo việc vài ns ra rác. Cách đo cho đáng tin.
Bài kết sê-ri: cùng một bài toán 'x có trong tập không', kẻ thắng đổi theo quy mô — quét tuyến tính nhanh nhất ở n=8, hash ở n lớn, bitset đè bẹp cả nếu biết miền khóa; và nhị phân O(log n) luôn kẹt giữa, không bao giờ nhanh nhất. Không có cấu trúc tốt nhất phổ quát — đo, đừng đoán.