Mỗi lớp độ phức tạp vẽ một đường cong
Vẽ biểu đồ chi phí so với kích thước đầu vào
Đặt kích thước đầu vào N trên trục x. Đặt chi phí (các phép tính, thời gian) trên trục y. Mỗi lớp độ phức tạp tạo ra một đường cong riên biệt. Bạn có thể nhận biết tốc độ tăng trưởng của thuật toán từ hình dạng của đường cong hiệu suất của nó.
O(1) — đường ngang phẳng. Hàm f(N) = 1. Không có độ dốc. Chi phí không bao giờ thay đổi bất kể N. Tìm kiếm bảng băm: dù bảng có chứa 10 hoặc 10.000.000 phần tử, một phép tính băm nhảy tới thùng chứa đúng.
O(log N) — đường cong hướng lên nhẹ nhàng, độ dốc giảm dần. Tại N = 1.000.000: chi phí ≈ 20 phép toán. Đường cong tăng dốc tại N nhỏ, rồi phẳng ra. Mỗi lần tăng gấp đôi N thêm đúng một đơn vị chi phí.
O(N) — đường thẳng chéo. Độ dốc = 1 (theo nghĩa tiệm cận). Chi phí tăng trưởng với tốc độ bằng N. Nếu N tăng gấp ba, chi phí cũng tăng gấp ba.
O(N log N) — đường chéo dốc hơn với độ cong hướng lên nhẹ. Nằm trên O(N) nhưng dưới O(N²). Hệ số log thêm một bộ nhân tăng trưởng chậm vào độ dốc tuyến tính.
O(N²) — đường parabol mở rộng hướng lên. Độ dốc tăng khi N tăng. Tại N = 10: chi phí = 100. Tại N = 100: chi phí = 10.000. Tại N = 1.000: chi phí = 1.000.000.
Khoảng cách ngày càng lớn
Tỷ lệ O(N²) / O(N) = N. Khoảng cách giữa đường parabol và đường chéo càng ngày càng rộng khi N tăng. Tại N = 10: khoảng cách 10×. Tại N = 100: khoảng cách 100×. Tại N = 1.000: khoảng cách 1.000×. Tại N = 50.000: khoảng cách 50.000×. Khoảng cách luôn bằng N.
Tính toán khoảng cách tỷ lệ
Một đồ thị phụ thuộc lớn chứa 50.000 gói (N = 50.000). Một thuật toán chạy trong thời gian O(N). Thuật toán thứ hai chạy trong O(N²). Tại N này, tỷ lệ O(N²)/O(N) = N = 50.000.
Chia đôi một đoạn đường thẳng
Tìm kiếm nhị phân dưới dạng chia đôi lặp lại
Một mảng đã sắp xếp với N phần tử tạo thành một đoạn đường thẳng có độ dài N. Tìm kiếm nhị phân chia đôi đoạn này lặp đi lặp lại:
1. Trỏ đến điểm giữa của đoạn còn lại.
2. Nếu target < điểm giữa: nửa phải biến mất. Đệ quy trên nửa bên trái.
3. Nếu target > điểm giữa: nửa bên trái biến mất. Đệ quy trên nửa bên phải.
4. Nếu target = điểm giữa: xong.
Sau k lần chia đôi, đoạn còn lại có độ dài N / 2^k. Tìm kiếm kết thúc khi độ dài đó bằng 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Vì vậy, tìm kiếm nhị phân trên N phần tử yêu cầu tối đa log₂N phép so sánh.
Chia đôi & tăng gấp đôi: Hai mặt của cùng một đường cong
Chia đôi và tăng gấp đôi là các nghịch đảo hình học. Đường cong hàm số mũ 2^k và đường cong lôgarit log₂N là phản ánh của nhau qua đường y = x.
Hãy xem xét việc gấp giấy: một tờ giấy bắt đầu với độ dày 0,1 mm. Mỗi lần gấp làm tăng gấp đôi độ dày. Sau 42 lần gấp: 0,1 mm × 2^42 ≈ 439.804 km — vượt quá mặt trăng (384.400 km). Tìm kiếm nhị phân chạy ngược lại: bắt đầu với N phần tử, mỗi bước chia đôi số lượng, đạt tới 1 phần tử trong log₂N bước.
Hình học: chia đôi là một phép toán tự tương tự. Mỗi lần chia đôi tạo ra hai nửa có cấu trúc giống hệt với toàn bộ. Đệ quy và lôgarit chia sẻ tính tự tương tự này.
So sánh & tăng gấp đôi
Một mảng đã sắp xếp chứa 1.048.576 phần tử. Lưu ý: 1.048.576 = 2^20.
Một hàm băm dưới dạng ánh xạ hình học
Hàm Băm như một Hàm
Một bảng băm ánh xạ một khóa tới một thùng chứa bằng cách sử dụng một hàm băm:
bucket = hash(key) mod table_size
Đây là một hàm theo nghĩa toán học chặt chẽ: nó ánh xạ một miền (tất cả các khóa có thể) tới một phạm vi (chỉ mục thùng chứa từ 0 đến table_size − 1). Hình ảnh hình học: khóa chiếm một không gian; thùng chứa chiếm một không gian khác. Hàm băm chiếu các khóa lên các chỉ mục thùng chứa.
O(1) tìm kiếm — nhảy trực tiếp, không tìm kiếm. Hàm băm tính toán chỉ mục thùng chứa trong thời gian không đổi. Nhảy trực tiếp tới thùng chứa đó. Không có duyệt, không có vòng lặp so sánh.
Hệ số tải. Tại hệ số tải 0,75, 75% các thùng chứa chứa ít nhất một phần tử. Trên ~0,9, các xung đột tăng lên: hai khóa được băm vào cùng một thùng chứa, tạo thành một chuỗi các phần tử bên trong thùng chứa đó. Tìm kiếm trong một chuỗi dài suy giảm thành O(N) trong trường hợp tồi tệ nhất.
Chất lượng phân bố dưới dạng Hình học
Một hàm băm được phân bố tốt phân tán các khóa đều trên tất cả các thùng chứa. Hình học: phạm vi của hàm bao phủ codomain của nó đều. Mỗi thùng chứa nhận xấp xỉ N / table_size khóa.
Một hàm băm kém cụm các khóa vào một vài thùng chứa. Hình học: phạm vi của hàm sụp đổ thành một tập con của codomain — hầu hết các khóa ánh xạ tới cùng một vài điểm. Các thùng chứa còn lại trống rỗng.
Kết nối với MOAD-0001
Thay thế một danh sách bằng một tập hợp sửa MOAD-0001 vì một tập hợp sử dụng một bảng băm nội bộ. O(N) quét danh sách → O(1) tìm kiếm bảng băm. Hình học: duyệt tuyến tính dọc theo một trình tự biến thành một phép chiếu trực tiếp qua một hàm. Trình tự biến mất; hàm thay thế nó.
Phân tích một Hàm Băm được phân bố kém
Một bảng băm có 1.000 thùng chứa và 900 phần tử (hệ số tải 0,9). Một hàm băm kém gửi 500 phần tử đó đến cùng một thùng chứa.