Trường Hợp Tốt Nhất, Xấu Nhất & Trung Bình
Ba Cách Đo Lường Một Thuật Toán
Chi phí của mỗi thuật toán tùy thuộc vào dữ liệu đầu vào của nó. Hai đầu vào có cùng kích thước có thể tạo ra thời gian chạy rất khác nhau. Phân tích độ phức tạp hình thức hóa ba góc nhìn về biến thiên đó.
Trường hợp tốt nhất — Ω (Omega): dữ liệu đầu vào giúp thuật toán kết thúc nhanh nhất. Đối với tìm kiếm tuyến tính trên danh sách N mục: Ω(1) — mục tiêu nằm ở vị trí đầu tiên. Một so sánh, xong.
Trường hợp xấu nhất — O (Big O): dữ liệu đầu vào giúp thuật toán kết thúc chậm nhất. Đối với tìm kiếm tuyến tính: O(N) — mục tiêu nằm cuối danh sách, hoặc không xuất hiện. Mỗi phần tử đều cần kiểm tra.
Trường hợp trung bình — Θ (Theta): chi phí kỳ vọng trên tất cả các đầu vào có thể, giả định phân phối đều. Đối với tìm kiếm tuyến tính với mục tiêu có khả năng nằm ở bất kỳ vị trí nào trong N vị trí: Θ(N/2) = Θ(N). Hằng số 1/2 bị bỏ vì Theta biểu thị tăng trưởng tiệm cận chặt chẽ, không phải hệ số chính xác.
Tại Sao Trường Hợp Xấu Nhất Chiếm Ưu Thế
Các hệ thống phải xử lý trường hợp xấu nhất. Truy vấn cơ sở dữ liệu trung bình 10 ms nhưng thỉnh thoảng mất 60 giây tạo ra lỗi nhìn thấy được của người dùng. Các kỹ sư thiết kế cho các giới hạn trường hợp xấu nhất để hiệu suất luôn có thể dự đoán được bất kể dữ liệu đầu vào. Phân tích trường hợp trung bình có giá trị trong các bối cảnh xác suất, nhưng phân tích trường hợp xấu nhất đưa ra đảm bảo.
Phân Tích Trường Hợp Tìm Kiếm Nhị Phân
Tìm kiếm nhị phân chỉ hoạt động trên các mảng được sắp xếp. Ở mỗi bước: so sánh mục tiêu với phần tử ở điểm giữa. Nếu mục tiêu bằng điểm giữa, trả về nó. Nếu mục tiêu nhỏ hơn, gọi lại trên nửa bên trái. Nếu lớn hơn, gọi lại trên nửa bên phải.
Mỗi so sánh loại bỏ một nửa ứng cử viên còn lại.
Tăng Trưởng Bộ Nhớ & Tradeoff Thời Gian-Không Gian
Đếm Bộ Nhớ, Không Phải Thao Tác
Độ phức tạp thời gian đo lường số thao tác mà thuật toán thực hiện. Độ phức tạp không gian đo lường bộ nhớ bổ sung mà nó cấp phát ngoài dữ liệu đầu vào của nó. Cả hai đều quan trọng trong các hệ thống sản xuất: một thuật toán nhanh cấp phát O(N²) bộ nhớ sẽ hết máy chủ.
O(1) không gian: bộ nhớ bổ sung không đổi bất kể N. Một sắp xếp tại chỗ (ví dụ: sắp xếp chèn) hoán đổi các phần tử bên trong mảng gốc. Nó sử dụng một số biến tạm thời — O(1) bất kể mảng lớn như thế nào.
O(N) không gian: bộ nhớ tỷ lệ với kích thước đầu vào. Tạo bản sao mảng N phần tử yêu cầu N vị trí. Xây dựng bộ hash từ danh sách N chuỗi lưu trữ tới N mục.
O(N²) không gian: bộ nhớ tỷ lệ với N². Xây dựng ma trận liền kề N×N cho đồ thị có N đỉnh yêu cầu N² ô. Ở N = 10,000 đỉnh, đó là 10^8 mục — hàng trăm megabyte cho một lưới boolean đơn giản.
Tradeoff Thời Gian-Không Gian
Một trong những bước cơ bản trong thiết kế thuật toán: trao đổi không gian cho thời gian, hoặc thời gian cho không gian.
Bảng hash sử dụng O(N) không gian bổ sung để đạt O(1) tra cứu. Không có bảng hash, quét qua danh sách đạt O(N) tra cứu với O(1) không gian bổ sung. Bảng hash trả tiền bộ nhớ để mua tốc độ.
Ghi nhớ lưu trữ kết quả đã tính toán trước đó (O(N) hoặc không gian hơn) để tránh tính toán lại. Fibonacci đệ quy mà không ghi nhớ chạy trong thời gian O(2^N). Với ghi nhớ: O(N) thời gian và O(N) không gian. Đầu tư không gian giảm thời gian theo hàm mũ.
Từ Điển Hash vs Danh Sách Được Sắp Xếp
So sánh hai chiến lược để đếm số lần xuất hiện từ trong tài liệu gồm N từ:
Chiến lược A: một từ điển (bảng hash). Chèn mỗi từ; tăng số lượng của nó.
Chiến lược B: duy trì danh sách được sắp xếp của các từ được xem; sử dụng tìm kiếm nhị phân để kiểm tra tư cách thành viên trước khi chèn.
Phân Tích Được Khấu Hao: Phân Tán Chi Phí
Khi Chi Phí T偶Thốc Không Phá Hủy Hiệu Suất Trung Bình
Một số thao tác thỉnh thoảng tốn kém nhưng rẻ trên trung bình trên một chuỗi. Phân tích được khấu hao tính toán chi phí trung bình trên mỗi thao tác trên toàn bộ chuỗi — không phải chi phí trường hợp xấu nhất của một thao tác duy nhất.
Mảng động (Python list, Java ArrayList): bắt đầu với dung lượng 1. Khi đầy, gấp đôi dung lượng. Nhân đôi sao chép tất cả các phần tử hiện có: O(N) công việc cho một lần chèn. Nhưng việc nhân đôi hiếm khi xảy ra. Sau N lần chèn tổng cộng, có bao nhiêu hoạt động sao chép tổng cộng xảy ra?
Các lần nhân đôi xảy ra ở kích thước 1, 2, 4, 8, ..., N/2. Số lần sao chép: 1 + 2 + 4 + ... + N/2. Đây là một chuỗi hình học tính tổng thành N − 1 lần sao chép tổng cộng trên tất cả N lần chèn. Trung bình sao chép trên mỗi lần chèn: (N − 1) / N < 1, vì vậy O(1) được khấu hao trên mỗi lần chèn mặc dù O(N) chi phí trường hợp xấu nhất cho mỗi lần nhân đôi.
Tại Sao Phân Tích Được Khấu Hao Quan Trọng
Một hệ thống thỉnh thoảng tạm dừng để thay đổi kích thước, cân bằng lại hoặc nén một cấu trúc có thể dường như có các thao tác riêng lẻ đáng báo động về trường hợp xấu nhất. Phân tích được khấu hao cho thấy rằng cảnh báo là sai: các sự kiện tốn kém hiếm hoi được trả tiền bởi những sự kiện rẻ tiền. Hiểu chi phí được khấu hao ngăn chặn kỹ sư quá mức: thêm độ phức tạp để tránh thao tác O(N) hiếm hoi chỉ đóng góp O(1) được khấu hao là công việc lãng phí.
Đi sâu hơn: khóa học unhamming áp dụng phân tích độ phức tạp cho các lỗi thế giới thực trong phần mềm sản xuất. Xem The Missing Chapter: Algorithmic Complexity & MOAD-0001: The Sedimentary Defect.
Bảng Hash Chèn Được Khấu Hao
Một bảng hash bắt đầu trống và gấp đôi dung lượng bất cứ khi nào hệ số tải vượt quá 0,75. Chèn 1.000 phần tử kích hoạt chính xác 10 lần nhân đôi ở dung lượng 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.