Array là gì và độ phức tạp của các thao tác trên nó là gì?

Question

IT Interview Practice · Accepted Answer

**Array** là một khối bộ nhớ liền kề chứa các phần tử cùng kiểu, được đánh index từ `0`. Vì các phần tử nằm cạnh nhau, địa chỉ của phần tử `i` được tính trực tiếp là `base + i * elementSize`, cho **truy cập ngẫu nhiên O(1)**.

## Bố cục bộ nhớ

```text
index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
arr =   | 10  | 20  | 30  | 40  | 50  |
        +-----+-----+-----+-----+-----+
address: base  +4    +8    +12   +16   (số nguyên 4-byte)
```

## Ví dụ

```python
arr = [10, 20, 30, 40, 50]
x = arr[3]            # O(1) — tính index trực tiếp
arr.append(60)        # amortized O(1) (dynamic array)
arr.insert(0, 5)      # O(n) — dịch mọi phần tử sang phải
arr.pop(0)            # O(n) — dịch mọi phần tử sang trái
```

## Độ phức tạp

| Thao tác | Thời gian |
|---|---|
| Truy cập theo index | O(1) |
| Tìm kiếm (chưa sắp xếp) | O(n) |
| Append (dynamic) | O(1) amortized |
| Chèn/xóa ở đầu/giữa | O(n) |

## Đánh đổi

- **Điểm mạnh:** đánh index nhanh, thân thiện với cache (dữ liệu liền kề), chi phí bộ nhớ thấp.
- **Điểm yếu:** chèn/xóa ở giữa là O(n); array kích thước cố định cần sao chép để mở rộng.

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

Array là nền tảng dưới hầu hết các cấu trúc khác — string, hash table, heap, và dynamic list đều xây dựng trên chúng.

Tính cục bộ cache (cache locality) của chúng thường khiến một array "chậm hơn" theo Big-O lại vượt qua một cấu trúc dựa trên pointer "nhanh hơn" trong các benchmark thực tế.

Thao tác	Thời gian
Truy cập theo index	O(1)
Tìm kiếm (chưa sắp xếp)	O(n)
Append (dynamic)	O(1) amortized
Chèn/xóa ở đầu/giữa	O(n)

Bố cục bộ nhớ

Ví dụ

Độ phức tạp

Đánh đổi

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

Câu hỏi liên quan