Cấu trúc dữ liệu và cái giá thật của chúng

1 Cùng O(n) mà chậm 442 lần: bí mật cache của mảng vs linked list Tưởng duyệt mảng và danh sách liên kết tốn như nhau vì cùng O(n)? Tôi đo thử: duyệt 20 triệu phần tử, mảng 0,24ns/phần tử còn linked list 104ns — chậm 442 lần, vì mỗi con trỏ next là một cache miss còn mảng thì được prefetch. Big-O đếm số thao tác, không đếm giá mỗi thao tác. 03/09/2026 · 8 phút đọc

2 push_back nhanh nhờ một phép nhân đôi: bí mật amortize của vector Tưởng mỗi push_back copy cả mảng nên vector chậm, hoặc grow-by-1 tiết kiệm RAM nên tốt? Tôi đo thử: nhân đôi amortize xuống 2,57ns/push (O(1)) xây 20 triệu phần tử, còn grow-by-1 là O(N²) — chỉ 50 nghìn phần tử đã 1,25 tỷ copy, 3213ns/push, nếu 20 triệu thì mất 7 giờ. 03/09/2026 · 8 phút đọc

3 Linked list chèn O(1)? Chỉ khi bạn đã đứng sẵn ở đúng chỗ Ai cũng thuộc 'linked list chèn/xóa O(1), mảng O(N)'. Tôi đo thử: chèn ở đầu list nhanh hơn mảng 70.000 lần — nhưng chèn giữa THỰC TẾ (phải tìm vị trí trước) thì list lại chậm hơn mảng 16 lần, vì duyệt để tìm là cache miss mỗi bước. O(1) chỉ đúng khi đã cầm sẵn con trỏ. 03/09/2026 · 8 phút đọc

4 Hash table O(1) — cho tới khi bạn để nó đầy 99% Ai cũng nói hash table là O(1). Tôi đo thử: O(1) chỉ đúng khi hệ số tải thấp — tải 0,25 tốn 1,17 probe (3,2ns), nhưng đẩy tải lên 0,99 thì probe trung bình nổ lên 43 và tra cứu chậm 10 lần. O(1) là trung bình có điều kiện, không phải bảo đảm vô điều kiện. 03/09/2026 · 9 phút đọc

5 Cùng tải 0,70, đổi hàm băm: hash table chậm đi 23 lần Phần 4 cho thấy tải cao giết hash table. Nhưng tôi đo tiếp: ngay ở CÙNG tải 0,70, đổi hàm băm tốt sang xấu làm probe trung bình nhảy từ 2,17 lên 358,9 — tra cứu chậm 23 lần. Băm hằng số thì thoái hóa hoàn toàn về O(n). Tải thấp là điều kiện cần, không đủ. 03/09/2026 · 9 phút đọc

6 Hash nhanh hơn cây 32 lần — nhưng thua 7000 lần ở range query O(1) < O(log n), nên hash luôn hơn cây? Tôi đo thử: tra cứu điểm hash nhanh hơn cây đỏ-đen 32 lần (16ns vs 518ns). Nhưng range query — tìm mọi phần tử >= x theo thứ tự — cây làm trong 7,8µs còn hash phải sort lại toàn bộ, 54,2ms. 'Cái nào nhanh hơn' là câu hỏi sai; chọn theo loại truy vấn. 03/09/2026 · 8 phút đọc

7 Dữ liệu đã sắp xếp giết cây tìm kiếm: khi O(log n) tụt xuống O(n) BST tra cứu O(log n)? Chỉ khi cây cân bằng. Tôi đo thử: chèn dữ liệu ĐÃ sắp xếp vào một BST thường làm cây lệch thành chuỗi cao đúng bằng N (50.000), tra cứu chậm hơn std::map 461 lần và xây cây chậm 594 lần. Dữ liệu sắp xếp — thứ trông đẹp nhất — hóa ra là worst case, không phải best. 03/09/2026 · 8 phút đọc

8 Vì sao mọi CSDL dùng B-tree chứ không cây nhị phân — dù cùng O(log n) Cây nhị phân và B-tree đều O(log n) — vậy sao mọi cơ sở dữ liệu dùng B-tree? Tôi đo thử: tra cứu 4 triệu khóa, cây nhị phân đi 22 tầng (887ns), B-tree fanout 64 chỉ 4 tầng (153ns) — nhanh 5,8 lần. Mỗi tầng là một lần chạm bộ nhớ (hay một lần đọc đĩa), nên ít tầng thắng. Cùng O(log n), khác cơ số log. 03/09/2026 · 9 phút đọc

9 Xây heap: make_heap nhanh hơn push từng cái tới 6,3 lần Xây một heap từ n phần tử — push từng cái cũng như make_heap chứ gì? Tôi đo thử: n lần push là O(n log n), còn heapify bottom-up là O(n); với dữ liệu xấu nhất heapify nhanh hơn 6,3 lần. Và bất ngờ: heap không cần cây con trỏ — nó chỉ là một mảng liền mạch. 03/09/2026 · 8 phút đọc

10 Cùng O(1) mà chậm 13 lần: cái giá malloc ẩn trong stack/queue Stack và queue đều O(1) push/pop dù cài bằng mảng hay linked list — chọn cách nào cũng vậy? Tôi đo thử: stack bằng mảng 0,3ns/thao tác, bằng linked list 4,0ns — chậm 13 lần, vì linked list trả malloc+free (5,5ns) mỗi thao tác. Cùng O(1), khác hằng số cả chục lần. 03/09/2026 · 7 phút đọc

11 O(log n) mà thua O(n): tìm nhị phân không phải lúc nào cũng thắng O(log n) < O(n), nên tìm nhị phân luôn thắng tuyến tính? Tôi đo thử: với mảng nhỏ, tuyến tính NHANH HƠN — điểm giao ở khoảng N≈32; dưới đó quét tuần tự thắng nhờ cache và không branch misprediction. Big-O là hành vi tiệm cận (N lớn); N nhỏ thì hằng số và phần cứng mới quyết định. 03/09/2026 · 8 phút đọc

12 Cùng dữ liệu, đổi cách xếp: nhanh 3,6 lần hoặc chậm 2 lần (SoA vs AoS) Bố cục struct chỉ là cách tổ chức, không đổi tốc độ? Tôi đo thử: duyệt một trường trên 15 triệu phần tử, SoA nhanh hơn AoS 3,6 lần vì cache line không bị lãng phí. Nhưng truy cập ngẫu nhiên mọi trường thì AoS lại nhanh gấp đôi. Không có bố cục nào luôn thắng — chọn theo mẫu truy cập. 03/09/2026 · 8 phút đọc

13 Hai biến độc lập vẫn chậm 5 lần: cái bẫy false sharing Hai luồng, mỗi luồng tăng bộ đếm riêng — độc lập hoàn toàn, phải chạy song song? Tôi đo thử: nếu hai bộ đếm nằm cùng một cache line, chúng chậm hơn 3,8–4,9 lần vì dòng cache ping-pong giữa hai lõi (false sharing). Tách sang cache line riêng (padding) là khắc phục. Không chia sẻ một byte dữ liệu nào vẫn bị phạt vì chung dòng. 03/09/2026 · 8 phút đọc

14 Đổi một dòng khai báo struct, tiết kiệm 33% RAM: bí mật của padding Thứ tự khai báo trường trong struct chỉ là chuyện phong cách? Tôi đo thử: đảo thứ tự cùng ba trường làm struct từ 24 byte xuống 16 byte — phí 33% RAM chỉ vì đệm căn lề, và duyệt mảng bản 16B nhanh hơn 1,35 lần vì nhét gấp đôi số struct mỗi cache line. Sắp trường lớn tới nhỏ. 03/09/2026 · 8 phút đọc

15 std::set hay bitset? Cùng một tập, chênh nhau tới 10.000 lần Cần một tập số nguyên, cứ dùng std::set cho tiện? Tôi đo thử: với miền nhỏ dày đặc, bitset nén RAM 192 lần, phép giao nhanh 10.000 lần (AND 64 phần tử mỗi lệnh), kiểm tra thành viên nhanh 870 lần. Nhưng miền rộng tập thưa thì bitset lại phí RAM — chọn theo miền nhỏ/rộng, dày/thưa. 03/09/2026 · 8 phút đọc

16 Hai dòng code biến union-find từ O(n) thành gần O(1) Union-find chỉ là đi lên gốc cây parent, đơn giản mà? Tôi đo thử: thiếu nén đường và union by rank, cây suy biến thành chuỗi và find thành O(n) — 28.368 ns/find. Thêm hai tối ưu, mỗi thao tác còn 3,8 ns, gần O(1) (α(n) — Ackermann ngược), nhanh hơn cả O(log n). 03/09/2026 · 8 phút đọc

17 s = s + x trong vòng lặp: quả bom O(N²) khiến 20 triệu ký tự mất 72 phút Nối chuỗi trong vòng lặp s = s + phần trông vô hại? Tôi đo thử: với chuỗi bất biến (tạo chuỗi mới mỗi lần), nối 200 nghìn ký tự đã copy 20 tỷ byte — O(N²), 2151 ns/ký tự; nếu 20 triệu thì mất 72 phút. Buffer/StringBuilder append tại chỗ chỉ 2,18 ns/ký tự, O(N) — nhanh hơn 1000 lần mỗi ký tự. 03/09/2026 · 7 phút đọc

18 Trie không 'tốt hơn' hash — nó làm được thứ hash chịu thua Trie luôn tốt hơn hash cho chuỗi? Tôi đo thử: trie tốn RAM gấp 11 lần hash (256 MB vs 23 MB) và exact match chỉ ngang nhau. Nhưng trie thắng tuyệt đối một việc hash không làm nổi: tra tiền tố / autocomplete — 94 lần nhanh hơn, vì hash phải quét toàn bộ tập. Chọn theo có cần prefix hay không. 03/09/2026 · 8 phút đọc

19 Cấu trúc cố tình trả lời sai — mà nhỏ hơn 26 lần: bloom filter Cấu trúc kiểm tra thành viên phải chính xác 100%? Tôi đo thử: bloom filter đổi ~0,82% dương tính giả (khớp công thức đến hai chữ số) lấy RAM ít hơn 26 lần và query nhanh 3,3 lần. Điều tài tình: nó không bao giờ sai về việc vắng — nói 'không có' là chắc chắn không có. 03/09/2026 · 8 phút đọc

20 Bỏ con trỏ, dùng chỉ số: cây nhỏ hơn 33% và nhanh hơn 1,86 lần Cây và list phải dùng con trỏ, đó là cách chuẩn? Tôi đo thử: thay con trỏ 8 byte bằng chỉ số 4 byte vào một arena làm node nhỏ hơn 33%, RAM ít hơn 33%, và tra cứu nhanh 1,86 lần — vì node nằm liền mạch thay vì malloc rải rác. Con trỏ không phải lựa chọn duy nhất, và thường không phải lựa chọn tốt nhất. 03/09/2026 · 8 phút đọc

21 LRU chỉ cần một map? Cái bẫy O(n) khiến cache lớn chậm 5862 lần LRU chỉ cần một map, quét tìm phần tử cũ khi đuổi? Tôi đo thử: quét map tìm phần tử ít dùng nhất là O(n) — cache 100 nghìn thì mỗi lần đuổi mất 128 µs, chậm 5862 lần bản đúng. LRU O(1) phải kết hợp hash map (tra O(1)) với danh sách liên kết đôi (thứ tự dùng O(1)). Sức mạnh nằm ở sự kết hợp. 03/09/2026 · 8 phút đọc

22 Ma trận kề nhìn gọn mà ngốn RAM 127 lần: bẫy đồ thị thưa Ma trận kề đơn giản nên cứ dùng? Tôi đo thử: với đồ thị thưa (đa số thực tế), ma trận tốn RAM gấp 127 lần và duyệt chậm 302 lần vì phải quét cả V² ô. Danh sách kề chỉ lưu cạnh thật. Nhưng ma trận lại thắng khi cần hỏi 'có cạnh (i,j) không' — O(1). Chọn theo mật độ đồ thị. 03/09/2026 · 8 phút đọc

23 BFS ngốn RAM 500 lần, DFS thì segfault: bộ nhớ theo hình dạng đồ thị BFS và DFS chỉ khác thứ tự duyệt, bộ nhớ như nhau? Tôi đo thử: trên cây phân nhánh cao, hàng đợi BFS giữ 1 triệu đỉnh cùng lúc còn ngăn xếp DFS chỉ 1.999 — chênh 500 lần. Trên đồ thị sâu, DFS đệ quy tràn stack và sập ở độ sâu ~500 nghìn. Bộ nhớ phụ thuộc hình dạng đồ thị, không phải cái nào cũng như nhau. 03/09/2026 · 8 phút đọc

24 std::sort hay stable_sort? Ba đánh đổi cái nút sort giấu đi Sắp xếp nào cũng như nhau, cứ std::sort? Tôi đo thử: sắp tại chỗ tốn ~0 bộ nhớ phụ nhưng không ổn định; sắp cấp thêm (merge) tốn 80 MB buffer cho 20 triệu int nhưng giữ thứ tự phần tử bằng nhau. Và quicksort pivot xấu trên dữ liệu đã sắp xếp thành O(n²), chậm 2428 lần. 03/09/2026 · 8 phút đọc

25 256 nhánh if-else chậm hơn bảng nhảy 121 lần — nhưng 4 nhánh thì không Nhiều if-else cũng nhanh như switch, compiler lo hết? Tôi đo thử: chuỗi quét tuyến tính là O(N) — 256 nhánh mất 35,57ns còn bảng nhảy 0,24ns, chậm 121 lần. Nhưng ở 2-4 nhánh, if-else viết tay ngang bảng, và phân bố lệch làm branch prediction gần miễn phí. Đây là một điểm giao, không phải câu trả lời một chiều. 03/09/2026 · 8 phút đọc

26 std::string không phải lúc nào cũng malloc: bí mật của SSO std::string luôn cấp phát heap nên chậm? Tôi đo thử: nhờ SSO, chuỗi ngắn (≤15 ký tự) lưu inline ngay trong đối tượng 32 byte, không malloc — tạo nhanh gấp 3 lần và copy nhanh gấp 5,3 lần chuỗi dài phải malloc. Phần lớn chuỗi thực tế đều ngắn nên chẳng bao giờ chạm heap. 03/09/2026 · 7 phút đọc

27 Move: trao chìa khóa thay vì xây lại cả căn nhà (nhanh 42.554 lần) Trả về hay gán một object lớn luôn tốn kém vì phải copy? Tôi đo thử: từ C++11, move chuyển sở hữu buffer trong O(1) — sao chép một vector 40 MB mất 1787µs còn move chỉ 0,042µs, nhanh hơn 42 nghìn lần. Copy nhân đôi buffer O(n), move chỉ chuyển con trỏ O(1). 03/09/2026 · 7 phút đọc

28 shared_ptr không miễn phí: cái giá atomic mỗi lần copy shared_ptr tiện nên cứ dùng khắp nơi? Tôi đo thử: mỗi lần copy shared_ptr là một phép đếm tham chiếu atomic, chậm gấp 2,3 lần gán con trỏ thô — và tệ hơn nữa khi nhiều luồng tranh cùng bộ đếm. Trong khi unique_ptr thì gần như miễn phí, nhanh bằng con trỏ thô. Chọn theo có cần chia sẻ sở hữu hay không. 03/09/2026 · 7 phút đọc

29 Cấp phát nhanh gấp 10 lần malloc bằng một mẹo cũ: arena malloc/free có phải cách cấp phát duy nhất, chi phí không tránh được? Tôi đo thử: một arena allocator cấp phát bằng cách chỉ tăng một con trỏ — nhanh gấp 10 lần malloc — và giải phóng cả lô 10 triệu đối tượng chỉ bằng một phép reset O(1) thay vì free 44 ms. Đổi lại nó không free lẻ được, chỉ hợp khi các đối tượng chết cùng lúc. 03/09/2026 · 8 phút đọc

30 Free lẻ mà vẫn nhanh 5,7 lần malloc: mẹo free list Arena nhanh nhưng không free lẻ được — muốn free từng cái thì đành quay lại malloc? Tôi đo thử: một pool free list cấp và free từng ô O(1) bằng cách xâu các ô trống vào một danh sách liên kết, churn nhanh gấp 5,7 lần malloc/free. Hay nhất là con trỏ next nhúng ngay trong ô trống nên tốn 0 byte thừa. 03/09/2026 · 10 phút đọc

31 free() rồi mà RAM không trả về: sự thật về phân mảnh heap free() xong là bộ nhớ trả về hệ điều hành ngay? Tôi đo thử: sau khi free 90% của 4 triệu ô nhỏ, RSS vẫn giữ 655 MB trong khi dữ liệu sống chỉ 55 MB — gấp 12 lần. Tệ hơn, những hố nhỏ rời rạc không lấp được request lớn hơn: cấp lại các ô 512B làm heap phình thêm 563 MB, còn cùng cỡ thì tái dùng đúng hố, +0 MB. 03/09/2026 · 10 phút đọc

32 8 triệu bản sao của 1000 chuỗi: interning cắt 732 MB xuống 30 Giữ nhiều bản sao của cùng một chuỗi thì tốn gì đâu? Tôi đo thử: 8 triệu tham chiếu tới chỉ 1000 giá trị duy nhất, nếu mỗi nơi giữ một bản riêng tốn 732 MB, còn interning (một bản duy nhất + chỉ số 4 byte) chỉ 30,8 MB — ít hơn 24 lần. Chưa hết: interning còn biến so sánh bằng thành so một số nguyên O(1), nhanh hơn 6,4 lần so từng ký tự. 03/09/2026 · 9 phút đọc

33 push_front vào vector: quả bom O(n) núp trên đường nóng Cần thêm phần tử ở đầu danh sách? Nhiều người bảo dùng vector cũng được. Tôi đo thử — và vector push_front hóa ra là O(n): mỗi lần thêm gấp đôi thời gian khi số phần tử gấp đôi (1552 → 3375 ns), vì nó phải dịch cả mảng. Một ring buffer chỉ lùi một chỉ số, O(1) (~3 ns), nhanh hơn 1136 lần ở N=100k. Còn std::deque thì push được hai đầu O(1), duyệt chỉ chậm hơn vector 19%. 03/09/2026 · 10 phút đọc

34 Skip list: O(log n) có thứ tự mà không cần một phép xoay Muốn một cấu trúc có thứ tự với tra cứu O(log n) thì bắt buộc phải cây cân bằng với logic xoay rắc rối? Đo ra: skip list đạt O(log n) kỳ vọng chỉ bằng tung đồng xu — chèn không xoay, code đơn giản hơn nhiều, chậm hơn std::map chỉ 8–12%. Nhưng nó không phải luôn thắng: cây đỏ-đen tối ưu kỹ vẫn nhanh hơn ở đơn luồng, và O(log n) của skip list chỉ là kỳ vọng. 03/09/2026 · 9 phút đọc

35 unordered_map dùng chaining — nhưng đó có phải cách nhanh nhất? std::unordered_map dùng chaining nên chaining là cách nhanh nhất xử lý va chạm? Đo ra: open addressing (dò trong một mảng liền) tra cứu nhanh hơn ở hệ số tải vừa (10,4 vs 15,1 ns ở tải 0,5) và gọn hơn 3,4 lần bộ nhớ. Nhưng ở tải 0,9, dò dồn cụm trung bình 5,45 lần khiến open chậm hẳn và chaining vượt lên — một điểm giao rõ ràng. 03/09/2026 · 8 phút đọc

36 Gói 4 trường vào 1 số: nhỏ 4 lần, shift/mask miễn phí Gói nhiều trường vào một từ chỉ tiết kiệm bộ nhớ mà làm chậm CPU vì shift/mask? Đo ra: một bản ghi 4 trường nhỏ gói vào một uint32 nhỏ hơn 4 lần (16 → 4 byte), và shift/mask khi đọc gần như miễn phí — duyệt khối lớn còn nhanh hơn 1,1 lần nhờ cache, mảng nóng thì hòa. Nhưng lợi ích chính là bộ nhớ, không phải tốc độ: throughput chỉ nhanh 1,1 lần chứ không tỉ lệ với mức nén. 03/09/2026 · 9 phút đọc

37 Serialize chỉ là copy byte? Text chậm hơn 52 lần Serialize chỉ là copy dữ liệu ra byte nên nhanh? Đo ra: binary memcpy đúng là gần như chỉ sao chép (0,48 ns/bản ghi, ~38 GB/s), nhưng ghi ra text từng trường chậm hơn 52 lần và parse chậm hơn 29 lần vì phải format/parse mỗi số. Còn binary memcpy nhanh thì lại không di động: endianness, padding, con trỏ đều vô nghĩa qua máy khác. 03/09/2026 · 9 phút đọc

38 Immutable chậm hay nhanh? Đảo chiều 100 lần tùy việc Immutable chậm vì cứ phải copy mỗi lần đổi? Đo ra: đúng một nửa — cập nhật một trường nhiều lần thì immutable naive chậm hơn mutable 101 lần (142,7 vs 1,4 ns) vì mỗi lần đổi phải copy cả đối tượng. Nhưng chia sẻ để đọc thì ngược lại: immutable chia sẻ tự do không tốn gì, còn mutable phải copy phòng thủ mỗi lần trao đi — chậm hơn immutable 97 lần. 03/09/2026 · 9 phút đọc

39 Giữ 1000 phiên bản mảng triệu phần tử mà không copy Giữ nhiều phiên bản của một cấu trúc thì phải copy cả nó mỗi lần sửa, tốn O(n)? Đo ra: một persistent vector kiểu trie nhánh 32 chỉ copy đường dẫn tới phần đổi — update nhanh hơn copy cả mảng 319 lần, và mỗi phiên bản mới tốn 1,76 KB thay vì 4 MB, ít hơn 2345 lần. Còn đọc thì chỉ chậm hơn mảng phẳng 1,1 lần vì nhánh rộng giữ cây nông. 03/09/2026 · 9 phút đọc

40 Lock-free không khóa nên nhanh hơn mutex? Tùy đông người Lock-free không dùng khóa nên luôn nhanh hơn mutex? Đo ra: với ít luồng thì atomic nhanh hơn hẳn (1 luồng mutex 4,1 ns vs atomic 1,6 ns), nhưng 8 luồng tranh gay gắt một biến thì atomic fetch_add chỉ ngang mutex (20,8 vs 22,1 ns) và CAS-loop tự viết tệ hơn mutex 6,8 lần (141,5 ns) vì thử lại liên tục. Và mutex không tranh chỉ tốn vài ns. 03/09/2026 · 8 phút đọc

41 Khi mảng quét O(n) đánh bại hash map O(1) Hash map O(1) nên luôn nhanh nhất cho tra cứu? Đo ra: với khóa chuỗi (băm phải đọc cả 24 ký tự ~10ns), quét tuyến tính một mảng nhỏ thắng hash map tới n≈16 — vì hằng số nhỏ hơn nhiều: cache liền, so sánh thoát sớm, không băm, không con trỏ. Big-O là tiệm cận n→vô cùng; ở n nhỏ chính hằng số quyết định, và điểm giao tùy giá của khóa. 03/09/2026 · 8 phút đọc

42 Vòng O(n) trông cong như O(n log n): thủ phạm là cache Cứ đo thời gian là biết ngay độ phức tạp? Đo ra: ở n nhỏ hằng số và overhead lấn át nên tỉ số T(2n)/T(n) lung tung (1,0/4,0/1,75), và cache tạo gãy khúc — truy cập ngẫu nhiên nhảy từ 0,9ns (L1) lên 96ns (RAM), khiến vòng O(n) trông siêu tuyến tính. Nhưng đo đúng cách thì tỉ số hội tụ chính xác: O(n)→2,00, O(n log n)→2,07. 03/09/2026 · 9 phút đọc

43 Không có cấu trúc dữ liệu tốt nhất — chỉ có đúng việc Có một cấu trúc dữ liệu tốt nhất, cứ dùng nó cho mọi thứ? Đo ra: trên cùng 100.000 phần tử, cấu trúc thắng đảo hoàn toàn theo mẫu truy cập — đọc/tra cứu thì hash map thắng (31 lần binary search), duyệt tuần tự thì mảng phẳng thắng (8–9 lần), chèn/xóa ở giữa thì linked list thắng (731 lần). Không có cấu trúc tốt nhất chung; mẫu truy cập quyết định. 03/09/2026 · 8 phút đọc

44 Benchmark đo ra 0 ns: bốn cái bẫy khiến số nói dối Chạy một lần bấm giờ là biết cấu trúc nào nhanh hơn? Đo ra bốn cái bẫy: lần chạy đầu chậm 1,5 lần (cache lạnh, page fault); nếu quên volatile SINK thì -O2 xóa sạch vòng lặp và đo ra 0 ns (số bịa); đo một thao tác đơn cho 84 ns rác (toàn overhead đồng hồ) so với 0,23 ns thật; và nhiễu OS chỉ làm chậm nên phải lấy min, không lấy trung bình. 03/09/2026 · 9 phút đọc

45 Cùng tổng O(n), một cách nhanh gấp 24 lần: lời kết sê-ri Kết sê-ri 45 phần bằng một phép đo gói trọn luận điểm: cùng 10 triệu số nguyên, cùng phép tính tổng O(n), nhưng mảng liền mạch chạy 0,225 ns mỗi phần tử còn mảng con trỏ rải rác 5,48 ns — chênh 24 lần chỉ vì cache và con trỏ, thứ mà Big-O hoàn toàn giấu. Bài học cả sê-ri: đừng đoán, hãy đo — và đo cho đúng. 03/09/2026 · 8 phút đọc