Algorithm (thuật toán) là gì?

Question

IT Interview Practice · Accepted Answer

**Algorithm** (thuật toán) là một chuỗi các bước hữu hạn, được định nghĩa rõ ràng, nhằm biến đổi đầu vào thành đầu ra mong muốn. Chúng ta đánh giá nó trên hai khía cạnh: **tính đúng đắn** (nó có luôn cho ra kết quả đúng không?) và **hiệu năng** (nó tốn bao nhiêu thời gian và bộ nhớ?).

## Ý tưởng

Một thuật toán hợp lệ phải *không mơ hồ* (mỗi bước đều rõ ràng), *hữu hạn* (nó kết thúc), và cho ra kết quả *đúng* với mọi đầu vào hợp lệ.

## Ví dụ

```python
# Tìm giá trị lớn nhất trong một danh sách
def find_max(nums):
    if not nums:
        return None          # xử lý đầu vào rỗng
    largest = nums[0]        # giả định phần tử đầu là lớn nhất
    for n in nums[1:]:       # quét phần còn lại
        if n > largest:
            largest = n      # cập nhật khi gặp giá trị lớn hơn
    return largest

find_max([3, 9, 2, 7])       # -> 9
```

Hàm này duyệt qua mỗi phần tử đúng một lần.

## Độ phức tạp

- **Thời gian:** O(n) — một lần duyệt qua n phần tử.
- **Bộ nhớ:** O(1) — chỉ một biến phụ.

## Khi nào quan trọng / những cạm bẫy

Cùng một bài toán có thể có nhiều thuật toán với chi phí khác nhau. Luôn kiểm tra các trường hợp biên (đầu vào rỗng, một phần tử, phần tử trùng lặp) — đó là nơi tính đúng đắn thường bị phá vỡ.

## Tại sao điều này quan trọng

Thuật toán là cốt lõi của việc giải quyết vấn đề trong phần mềm.

Hai chương trình có thể cho ra cùng một đáp án nhưng một chương trình có thể nhanh hơn hàng nghìn lần.

Tư duy theo hướng tính đúng đắn *và* hiệu năng là điều phân biệt giữa code chỉ chạy được trên một test case và code chạy được ở quy mô lớn.

Đây cũng là ngôn ngữ chung của các buổi phỏng vấn kỹ thuật và các cuộc thảo luận thiết kế hệ thống.

Ý tưởng

Ví dụ

Độ phức tạp

Khi nào quan trọng / những cạm bẫy

Tại sao điều này quan trọng

Câu hỏi liên quan