1. Bản chất Toán học & Mô hình Thực tế

Trong tin học, Cấu trúc dữ liệu (Data Structure) và Giải thuật (Algorithm) là hai khía cạnh không thể tách rời:

• Cấu trúc dữ liệu: Cách thức tổ chức, lưu trữ và quản lý dữ liệu trong bộ nhớ (RAM) sao cho các thao tác trên dữ liệu đó được thực hiện hiệu quả nhất.

• Giải thuật: Dãy các chỉ thị logic từng bước để giải quyết một bài toán cụ thể từ dữ liệu đầu vào (Input) để cho ra kết quả đầu ra (Output).

Công thức kinh điển của Niklaus Wirth:

$$\text{Chương trình} = \text{Cấu trúc dữ liệu} + \text{Giải thuật}$$

Bài toán thực tế: Tìm kiếm thông tin khách hàng trong Cơ sở dữ liệu

Giả sử hệ thống quản lý của anh lưu trữ danh sách $N = 1.000.000$ (1 triệu) mã hồ sơ. Anh cần tìm xem mã $X$ có tồn tại trong hệ thống hay không.

• Cách 1 (Mảng chưa sắp xếp + Tìm kiếm tuyến tính):

  Máy tính phải duyệt qua từng hồ sơ từ đầu đến cuối. Nếu mã $X$ nằm ở vị trí cuối cùng, máy tính phải thực hiện $1.000.000$ phép so sánh.

• Cách 2 (Mảng đã sắp xếp + Tìm kiếm nhị phân):

  Nhờ dữ liệu có cấu trúc thứ tự, tại mỗi bước ta so sánh $X$ với phần tử ở giữa và loại bỏ ngay $50\%$ số phần tử còn lại. Số phép so sánh tối đa chỉ là:

  $$\log_2(1.000.000) \approx 20 \text{ phép so sánh.}$$

Sự chênh lệch giữa $1.000.000$ bước và $20$ bước chính là lý do vì sao một thuật toán tốt có thể giúp hệ thống chạy nhanh hơn hàng nghìn lần mà không cần nâng cấp phần cứng.

2. Sơ đồ Tư duy: Mối quan hệ giữa Cấu trúc Dữ liệu và Thao tác

                  [ TẬP DỮ LIỆU ĐẦU VÀO ]
                            |
           +----------------+----------------+
           |                                 |
 [ Cấu trúc Dữ liệu A ]            [ Cấu trúc Dữ liệu B ]
  (VD: Mảng tuyến tính)             (VD: Cây tìm kiếm nhị phân)
           |                                 |
           v                                 v
 [ Giải thuật Tìm kiếm A ]         [ Giải thuật Tìm kiếm B ]
   (Tốn tối đa N bước)              (Tốn tối đa log2(N) bước)

3. Mã nguồn Minh họa (Python)

Đoạn mã dưới đây mô phỏng sự chênh lệch hiệu năng giữa hai cách tiếp cận:

import time

# Tạo tập dữ liệu gồm 10 triệu phần tử đã sắp xếp
N = 10_000_000
data = list(range(N))
target = 9_999_999  # Phần tử cần tìm nằm ở cuối danh sách


# Cách 1: Tìm kiếm tuyến tính (Linear Search) - O(N)
def linear_search(arr, key):
    for item in arr:
        if item == key:
            return True
    return False


# Cách 2: Tìm kiếm nhị phân (Binary Search) - O(log N)
def binary_search(arr, key):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return True
        elif arr[mid] < key:
            left = mid + 1
        else:
            right = mid - 1
    return False


# Đo thời gian chạy Linear Search
start_time = time.time()
linear_search(data, target)
print(f"Linear Search execution time: {time.time() - start_time:.6f} seconds")

# Đo thời gian chạy Binary Search
start_time = time.time()
binary_search(data, target)
print(f"Binary Search execution time: {time.time() - start_time:.6f} seconds")