Cho một dãy gồm 10⁹ số nguyên được lưu trên ổ cứng.
RAM chỉ có 512 MB.
Hãy đề xuất thuật toán để tìm 100 số lớn nhất với số lần truy cập ổ cứng ít nhất.
Phân tích độ phức tạp.

Question

cute · Accepted Answer

Để tìm 100 số lớn nhất từ dãy $10^{9}$ số nguyên lưu trên ổ cứng với RAM giới hạn 512 MB, thuật toán tối ưu nhất là sử dụng Cấu trúc dữ liệu Min-Heap (Đống tối thiểu) kết hợp với Đọc dữ liệu theo khối (Stream/Buffer).

Giải pháp này chỉ cần truy cập ổ cứng đúng 1 lần duy nhất (đọc tuần tự từ đầu đến cuối).

1. Đề xuất thuật toán

• Khởi tạo: Tạo một cấu trúc dữ liệu Min-Heap có kích thước tối đa là 100 phần tử.

• Đọc dữ liệu: Đọc tuần tự từng khối dữ liệu (ví dụ: mỗi lần đọc một khối vài megabyte) từ ổ cứng vào RAM để tối ưu hóa tốc độ I/O.

• Xử lý từng số $x$ trong luồng dữ liệu:

o Nếu Min-Heap chưa đủ 100 phần tử: Thêm trực tiếp $x$ vào Min-Heap.

o Nếu Min-Heap đã có đủ 100 phần tử: So sánh $x$ với phần tử nhỏ nhất hiện tại ở đỉnh heap (heap[0]). Nếu $x > \text{heap}[0]$, ta loại bỏ heap[0] và thêm $x$ vào heap, sau đó thực hiện vun đống phục hồi tính chất Min-Heap. Nếu $x \le \text{heap}[0]$, bỏ qua $x$.

• Kết quả: Sau khi đọc hết $10^{9}$ số, 100 phần tử còn lại trong Min-Heap chính là 100 số lớn nhất cần tìm.

2. Phân tích độ phức tạp

• Độ phức tạp thời gian (Time Complexity): $\mathcal{O}(N \log K)$

o Với $N = 10^9$ và $K = 100$. Vì $K$ rất nhỏ, $\log_2(100) \approx 7$, chi phí cho mỗi lần cập nhật heap là cực kỳ nhỏ.

o Tổng số phép toán xấp xỉ $7 \times 10^9$ phép so sánh/hoán đổi trong trường hợp xấu nhất.

• Độ phức tạp không gian (Space Complexity): $\mathcal{O}(K)$ trong RAM

o Bộ nhớ lưu trữ Min-Heap chỉ tốn dung lượng cho 100 số nguyên (khoảng 400 bytes hoặc 800 bytes), hoàn toàn đáp ứng mức giới hạn 512 MB của RAM.

• Số lần truy cập ổ cứng: $\mathcal{O}(1)$

o Toàn bộ dữ liệu được đọc tuần tự theo cơ chế streaming từ đầu đến cuối một lần duy nhất, không cần ghi ngược lại hay tạo file tạm trên ổ cứng (External Sorting).

Bạn có muốn viết mã giả hay mô phỏng thuật toán này không?

Timi · Answer

Bài toán: Tìm 100 số lớn nhất trong dãy 10^9 số nguyên lưu trên ổ cứng, với RAM chỉ có 512 MB, và tối ưu số lần truy cập ổ cứng.

---

## Phân tích bài toán

- Dãy có 10^9 số nguyên, giả sử mỗi số nguyên 4 bytes, tổng kích thước ~4 GB.
- RAM chỉ có 512 MB, không thể load toàn bộ dữ liệu vào RAM.
- Cần tìm 100 số lớn nhất.
- Mục tiêu: giảm số lần truy cập ổ cứng (I/O) càng ít càng tốt.

---

## Đề xuất thuật toán

### Thuật toán sử dụng Min-Heap kích thước 100

1. **Khởi tạo** một Min-Heap (hàng đợi ưu tiên nhỏ nhất) có kích thước tối đa 100 phần tử trong RAM.

2. **Đọc dữ liệu theo từng block** từ ổ cứng vào RAM:
   - Kích thước block có thể là 10^7 số (40 MB), hoặc tối đa có thể trong RAM (512 MB) trừ bộ nhớ dùng cho heap và các biến khác.
   - Ví dụ: đọc 10^7 số mỗi lần, cần đọc 100 lần (10^9 / 10^7 = 100).

3. **Xử lý từng block**:
   - Với mỗi số trong block:
     - Nếu heap chưa đầy 100 phần tử, thêm số vào heap.
     - Nếu heap đã đầy, so sánh số hiện tại với phần tử nhỏ nhất trong heap (đỉnh heap):
       - Nếu số hiện tại lớn hơn, thay thế phần tử nhỏ nhất bằng số hiện tại và điều chỉnh heap.
       - Nếu nhỏ hơn hoặc bằng, bỏ qua.

4. **Kết thúc** sau khi đọc hết 10^9 số, heap chứa 100 số lớn nhất.

5. **Trích xuất** 100 số lớn nhất từ heap.

---

## Phân tích độ phức tạp

- **Số lần truy cập ổ cứng**: 
  - Đọc toàn bộ dữ liệu 10^9 số một lần, chia thành 100 block, mỗi block đọc một lần.
  - Tổng số lần truy cập ổ cứng: khoảng 100 lần đọc block (có thể giảm nếu tăng kích thước block).
  - Không cần ghi dữ liệu ra ổ cứng trong quá trình xử lý.

- **Độ phức tạp tính toán**:
  - Mỗi số được xử lý một lần.
  - Với mỗi số, thao tác trên heap kích thước 100 có độ phức tạp O(log 100) ≈ O(1).
  - Tổng thời gian xử lý: O(10^9 * log 100) ≈ O(10^9).

- **Bộ nhớ**:
  - Min-Heap kích thước 100 rất nhỏ, chiếm vài KB.
  - RAM còn lại dùng để đọc block dữ liệu.

---

## Tóm tắt

| Tiêu chí               | Đề xuất thuật toán Min-Heap |
|-----------------------|-----------------------------|
| Số lần truy cập ổ cứng | Khoảng 100 lần (đọc block)  |
| Bộ nhớ RAM            | 512 MB (dùng để đọc block)  |
| Độ phức tạp tính toán | O(10^9)                     |
| Độ phức tạp bộ nhớ    | O(100)                      |

---

Nếu cần giảm số lần truy cập ổ cứng hơn nữa, có thể tăng kích thước block đọc vào RAM (nếu RAM cho phép), hoặc dùng kỹ thuật phân vùng (partition) nhưng sẽ phức tạp hơn và có thể tăng số lần truy cập ổ cứng do ghi/đọc nhiều lần.

Bạn có muốn tôi giải thích thêm về các phương pháp khác hoặc chi tiết kỹ thuật?

Cho một dãy gồm 10⁹ số nguyên được lưu trên ổ cứng. RAM chỉ có 512 MB. Hãy đề xuất thuật toán để tìm 100 số lớn nhất với số lần truy cập ổ cứng ít nhất. Phân tích độ phức tạp.