Mảng (Array)Arrays

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Array là cấu trúc dữ liệu đơn giản nhất, và cũng là quan trọng nhất. Nó là một khối bộ nhớ liên tục (contiguous) chứa một số phần tử cố định có kích thước bằng nhau. Chỉ riêng đặc tính đó — liên tục, kích thước bằng nhau — mua được thứ mà không cấu trúc nào khác có được miễn phí: bạn có thể tính ra địa chỉ của phần tử i thay vì phải đi tìm nó.

address(A[i]) = base_address + i * element_size

Một phép nhân, một phép cộng, một lần đọc bộ nhớ. Thời gian hằng số, bất kể array có 10 phần tử hay 10 tỷ phần tử. Mọi cấu trúc “random access” khác trong bộ kiến thức này — hash table, binary heap, Fenwick tree, adjacency matrix, page cache của database — suy cho cùng đều là một array với một lược đồ đánh địa chỉ chồng lên trên. Hiểu array cho tử tế thì một nửa phần còn lại chỉ là ghi sổ.

Cái giá của tính liên tục đó là sự cứng nhắc. Vì các phần tử nằm sát vai nhau, không có khoảng trống ở giữa, bạn không thể chèn vào giữa mà không dịch chuyển tất cả những gì phía sau, và không thể mở rộng quá cuối khối mà không đi tìm một khối lớn hơn rồi copy sang. Array đánh đổi tính linh hoạt lấy tốc độ, và toàn bộ không gian thiết kế “dùng cấu trúc nào ở đây” phần lớn là câu hỏi liệu đánh đổi đó có đáng với access pattern của bạn hay không.

Note này bao quát cả hai nửa của câu chuyện: static array (dung lượng cố định, thứ mà C gọi là int a[100] và là thứ thực sự tồn tại ở tầng phần cứng), và dynamic array (list của Python, vector của C++, ArrayList của Java, slice của Go) — vốn chỉ là một static array được giấu sau một chính sách tự động tăng trưởng. Chúng ta sẽ dựng dynamic array từ đầu, vì list của Python vốn đã là một dynamic array rồi và dùng nó để dạy chính nó thì chẳng giải thích được gì.

Kiến thức nền tảng

Memory layout

Một static array gồm năm số nguyên 4 byte, bắt đầu tại địa chỉ 0x1000:

       index:     0        1        2        3        4
                +--------+--------+--------+--------+--------+
   memory:      |   17   |    3   |   99   |   42   |    8   |
                +--------+--------+--------+--------+--------+
     address:    0x1000   0x1004   0x1008   0x100C   0x1010
                    ^
                    base

   A[3]  ->  0x1000 + 3 * 4  =  0x100C   ->  42       O(1), một phép tính địa chỉ

Hai hệ quả xuất hiện ngay lập tức:

• Random access là O(1). Không traversal, không so sánh, không đuổi theo pointer. CPU tính địa chỉ và phát ra đúng một lệnh load.
• Không có chỗ trống giữa các phần tử. Chèn 55 vào index 2 nghĩa là dời 99, 42, 8 sang phải một ô — O(n) lần ghi. Xoá index 2 nghĩa là dời chúng sang trái một ô. Chúng không có chỗ nào khác để đi.

Đây chính xác là điều ngược lại với linked list, nơi các phần tử có thể nằm bất cứ đâu trong bộ nhớ nhưng bạn phải đi hết chuỗi mới tới được phần tử thứ n.

Static array và dynamic array

	Static array	Dynamic array
Dung lượng	Cố định lúc tạo	Tự động tăng
Ví dụ	C int a[100], Java int[], NumPy ndarray, Go [5]int	Python list, C++ std::vector, Java ArrayList, Go slice, Rust Vec
Lưu trữ	Chính khối bộ nhớ đó	Một pointer tới khối + size + capacity
Append	Không thể vượt quá cuối khối	O(1) amortized
Overhead bộ nhớ	Không có	Lãng phí tới ~50% capacity (với tăng trưởng 2×)

Dynamic array không phải một cấu trúc dữ liệu khác. Nó là một static array cộng thêm hai số nguyên và một chính sách:

   DynamicArray:  size = 5,  capacity = 8

                +----+----+----+----+----+----+----+----+
     _data ---> | 17 |  3 | 99 | 42 |  8 |    |    |    |
                +----+----+----+----+----+----+----+----+
                  0    1    2    3    4    ^^^^^^^^^^^^
                                            phần dư: đã cấp phát nhưng chưa dùng

   append(23):  size < capacity, chỉ cần ghi rồi tăng size  ->  O(1)
   append(...) khi size == capacity:
        cấp phát khối mới capacity*2, copy toàn bộ n phần tử, giải phóng khối cũ  ->  O(n)

Độ phức tạp

Thao tác	Static array	Dynamic array (trung bình)	Dynamic array (worst case)	Lý do
Truy cập A[i]	O(1)	O(1)	O(1)	Tính địa chỉ số học
Cập nhật A[i] = x	O(1)	O(1)	O(1)	Tính địa chỉ số học
Append ở cuối	—	O(1) amortized	O(n)	Worst case là lúc resize và copy
Chèn ở đầu	—	O(n)	O(n)	Dịch cả n phần tử sang phải
Chèn tại index i	—	O(n − i)	O(n)	Dịch phần đuôi
Xoá ở cuối (pop)	—	O(1) amortized	O(1)	Chỉ giảm size
Xoá ở đầu	—	O(n)	O(n)	Dịch cả n − 1 phần tử sang trái
Tìm kiếm (chưa sort)	O(n)	O(n)	O(n)	Phải duyệt hết mọi phần tử
Tìm kiếm (đã sort)	O(log n)	O(log n)	O(log n)	Binary search
Bộ nhớ	O(n)	O(n)	O(n)	Hệ số 1×–2× với dynamic

Vì sao là “amortized” chứ không phải O(1) thuần: một lần append đơn lẻ có thể tốn O(n) khi nó kích hoạt resize. Nhưng những lần append đắt đỏ đó hiếm đến mức trung bình trên cả một chuỗi thao tác vẫn là hằng số. Sự phân biệt đó được triển khai trong độ phức tạp thuật toán và được chứng minh bên dưới.

Dựng dynamic array từ đầu

list của Python vốn đã là dynamic array, nên để thấy được cơ chế bên trong ta cần một array kích thước cố định thật sự làm nền. ctypes cho ta điều đó — một khối capacity ô thật, không thể tự lớn lên:

import ctypes


class DynamicArray:
    """Dynamic array dựng trên một raw array dung lượng cố định, tự nhân đôi thủ công."""

    GROWTH_FACTOR = 2

    def __init__(self):
        self._n = 0                                # số phần tử thực sự đang chứa
        self._capacity = 1                         # số ô đã cấp phát
        self._data = self._make_array(self._capacity)

    @staticmethod
    def _make_array(capacity):
        """Cấp phát một khối raw, cố định `capacity` ô. Không thể tự lớn lên."""
        return (capacity * ctypes.py_object)()

    def __len__(self):
        return self._n

    def __getitem__(self, i):
        if not 0 <= i < self._n:                   # bỏ qua index âm cho gọn
            raise IndexError("index out of range")
        return self._data[i]                       # O(1) — tính địa chỉ số học

    def __setitem__(self, i, value):
        if not 0 <= i < self._n:
            raise IndexError("index out of range")
        self._data[i] = value                      # O(1)

    def append(self, value):
        """O(1) amortized: O(1) hầu hết thời gian, O(n) khi phải resize."""
        if self._n == self._capacity:              # đã đầy — không còn ô dư
            self._resize(self._capacity * self.GROWTH_FACTOR)
        self._data[self._n] = value
        self._n += 1

    def _resize(self, new_capacity):
        """O(n): cấp phát khối lớn hơn rồi copy từng phần tử sang."""
        new_data = self._make_array(new_capacity)
        for i in range(self._n):                   # chính vòng copy này tốn O(n)
            new_data[i] = self._data[i]
        self._data = new_data                      # khối cũ trở thành rác
        self._capacity = new_capacity

    def insert(self, i, value):
        """O(n): mọi phần tử từ index i trở đi phải dịch sang phải một ô."""
        if not 0 <= i <= self._n:
            raise IndexError("index out of range")
        if self._n == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)
        for j in range(self._n, i, -1):            # đi ngược để không ghi đè lên dữ liệu
            self._data[j] = self._data[j - 1]
        self._data[i] = value
        self._n += 1

    def pop(self, i=None):
        """O(1) ở cuối, O(n) ở mọi vị trí khác — phần đuôi phải lấp chỗ trống."""
        if self._n == 0:
            raise IndexError("pop from empty array")
        if i is None:
            i = self._n - 1
        if not 0 <= i < self._n:
            raise IndexError("index out of range")
        value = self._data[i]
        for j in range(i, self._n - 1):            # dịch phần đuôi sang trái
            self._data[j] = self._data[j + 1]
        self._n -= 1
        # Thu nhỏ khi còn 1/4, không phải 1/2 — xem phần "hysteresis" bên dưới
        if 0 < self._n <= self._capacity // 4:
            self._resize(max(1, self._capacity // 2))
        return value

    def __iter__(self):
        for i in range(self._n):
            yield self._data[i]

    def __repr__(self):
        return f"DynamicArray({list(self)}, capacity={self._capacity})"


arr = DynamicArray()
for x in [17, 3, 99, 42, 8]:
    arr.append(x)
print(arr)              # DynamicArray([17, 3, 99, 42, 8], capacity=8)
arr.insert(2, 55)
print(arr)              # DynamicArray([17, 3, 55, 99, 42, 8], capacity=8)
print(arr.pop(0), arr)  # 17 DynamicArray([3, 55, 99, 42, 8], capacity=8)

Vì sao nhân đôi cho ra O(1) amortized

Bắt đầu với capacity 1 và append n phần tử. Resize xảy ra tại size 1, 2, 4, 8, …, và mỗi lần resize tại size k phải copy k phần tử. Tổng công copy:

1 + 2 + 4 + 8 + ... + n/2 + n  <  2n

Một cấp số nhân công bội 2 có tổng nhỏ hơn hai lần số hạng lớn nhất. Vậy n lần append tốn O(n) tổng cộng cho việc copy cộng với O(n) cho chính các lần ghi — tức O(1) mỗi lần append theo nghĩa amortized.

Cách lập luận theo phương pháp kế toán (accounting method) trực quan hơn: tính 3 đơn vị chi phí cho mỗi lần append. Một đơn vị trả cho việc ghi phần tử; hai đơn vị còn lại được gửi tiết kiệm vào ô đó. Khi array nhân đôi từ k lên 2k, k/2 phần tử được thêm kể từ lần resize trước, mỗi phần tử mang theo 2 đơn vị tiết kiệm — vừa đúng k đơn vị, đủ trả cho việc copy cả k phần tử. Số dư tài khoản không bao giờ âm, nên chi phí amortized mỗi thao tác là hằng số 3.

Vì sao hệ số tăng trưởng lại quan trọng:

Hệ số	Công copy cho n lần append	Bộ nhớ lãng phí	Ghi chú
+1 (tăng một lượng hằng số)	1+2+…+n = O(n²)	~0	Thảm hoạ. Append là O(n), không phải O(1).
×1.125	O(n), hằng số lớn hơn	≤ 12%	Chính sách của CPython list: newsize + (newsize >> 3) + 6, có làm tròn.
×1.5	O(n)	≤ 33%	MSVC std::vector. Khối đã giải phóng có thể tái sử dụng cho lần cấp phát sau.
×2	O(n)	≤ 50%	libstdc++ std::vector, Go slice (×2 cho tới 256 phần tử).

Bất kỳ hệ số nào lớn hơn 1 đều cho ra O(1) amortized; chỉ hằng số thay đổi. Tăng theo một lượng cố định thì không — đó là lựa chọn sai thực sự duy nhất, và là một cái bẫy phỏng vấn kinh điển.

Hysteresis khi thu nhỏ. Để ý pop ở trên thu nhỏ khi còn 1/4 và chia đôi capacity. Nếu thay vào đó bạn thu nhỏ khi còn 1/2, một workload xen kẽ append/pop ngay tại ngưỡng sẽ resize ở mỗi một thao tác — O(n) mỗi lần gọi, mãi mãi. Khoảng cách giữa ngưỡng tăng (đầy 100%) và ngưỡng giảm (còn 25%) đảm bảo rằng sau bất kỳ lần resize nào, phải có Ω(n) thao tác nữa trước lần resize kế tiếp. Nhiều implementation (kể cả list của CPython) đơn giản là không bao giờ thu nhỏ.

Khái niệm chính

Cache locality — lý do array thắng trong thực tế

Mô hình RAM nói A[i] và A[j] tốn như nhau. Phần cứng thật không đồng ý, đôi khi lệch nhau tới 50 lần. Bộ nhớ được nạp theo cache line — thường là 64 byte — nên đọc A[0] sẽ kéo luôn A[0..15] (với int 4 byte) vào L1 cache miễn phí. Một lần quét tuần tự nhận được 15 lần hit miễn phí cho mỗi lần miss; một lần quét theo thứ tự ngẫu nhiên gần như miss ở mọi lần truy cập một khi array vượt quá kích thước cache.

   Quét tuần tự một array int (cache line 64 byte, int 4 byte):

   miss  hit hit hit ... hit   miss  hit hit hit ... hit
   [ A[0] A[1] ... A[15] ]     [ A[16] ... A[31] ]
   \___ một cache line ____/   \___ một cache line ___/

   -> 1 lần nạp bộ nhớ cho mỗi 16 phần tử, chưa kể prefetcher thấy được bước nhảy
      và nạp sẵn line kế tiếp trước cả khi bạn yêu cầu.

   Duyệt linked list:

   node ---> ??? ---> ??? ---> ???      mỗi `next` là một địa chỉ không đoán trước được
   miss      miss     miss     miss     -> không prefetch, ~1 lần nạp bộ nhớ mỗi phần tử

Độ trễ xấp xỉ trên CPU hiện đại: L1 hit ~1 ns, L2 ~4 ns, L3 ~15 ns, RAM chính ~80–100 ns. Chính khoảng chênh đó là lý do một lần quét O(n) trên array liên tục thường xuyên thắng một lần tìm O(log n) trên cây dựa trên pointer với n nhỏ đến trung bình, và là lý do các implementation thực tế của những cấu trúc “lớn” (B-tree, hash table, heap) đều được dựng trên array. Đó cũng là lý do database lưu row trong các page kích thước cố định — xem storage internals.

import time

n = 20_000_000
data = list(range(n))
index = list(range(n))

start = time.perf_counter()
total = 0
for i in index:                      # tuần tự: locality hoàn hảo
    total += data[i]
sequential = time.perf_counter() - start

import random
random.shuffle(index)
start = time.perf_counter()
total = 0
for i in index:                      # cùng số phép toán, nhưng thứ tự địa chỉ ngẫu nhiên
    total += data[i]
shuffled = time.perf_counter() - start

print(f"sequential {sequential:.2f}s vs shuffled {shuffled:.2f}s")
# Thường chậm hơn 3-10 lần khi xáo trộn, với cùng một lượng công việc O(n).

Một lưu ý riêng cho Python: list của CPython là một array các pointer trỏ tới object, không phải array các giá trị. Các pointer thì liên tục; các số nguyên mà chúng trỏ tới thì nằm rải rác trên heap. Bạn được một tầng locality, không phải hai. ndarray của NumPy lưu giá trị thô liên tục và là công cụ đúng khi locality thực sự quan trọng.

Mảng hai chiều

Ở tầng phần cứng không tồn tại thứ gọi là mảng 2 chiều — bộ nhớ là một chiều. Mảng 2 chiều là một mảng 1 chiều cộng với một công thức index.

   Ma trận 3x4 về mặt logic:

        col:  0   1   2   3
   row 0:   [ a   b   c   d ]
   row 1:   [ e   f   g   h ]
   row 2:   [ i   j   k   l ]

   Row-major layout (C, C++, Python/NumPy mặc định, Java):
   [ a b c d | e f g h | i j k l ]
     M[r][c] = flat[r * COLS + c]

   Column-major layout (Fortran, MATLAB, R, bên trong BLAS):
   [ a e i | b f j | c g k | d h l ]
     M[r][c] = flat[c * ROWS + r]

Layout quyết định thứ tự duyệt nào là nhanh. Với lưu trữ row-major, duyệt theo row-rồi-column là đi tuần tự trong bộ nhớ; duyệt theo column-rồi-row thì nhảy COLS * element_size byte mỗi bước, chạm vào một cache line mới mỗi lần.

def flat_matrix(rows, cols, fill=0):
    """Mảng 2 chiều thật sự: một khối liên tục, index theo row-major."""
    return {"rows": rows, "cols": cols, "data": [fill] * (rows * cols)}


def get(m, r, c):
    return m["data"][r * m["cols"] + c]          # công thức index, O(1)


def set_(m, r, c, value):
    m["data"][r * m["cols"] + c] = value


m = flat_matrix(3, 4)
set_(m, 1, 2, 99)
print(get(m, 1, 2))        # 99
print(m["data"])           # [0,0,0,0, 0,0,99,0, 0,0,0,0] — khối row-major


# "Mảng 2 chiều" thông thường trong Python là list của list — KHÔNG liên tục.
# Mỗi row là một lần cấp phát heap riêng; list ngoài chỉ chứa pointer tới chúng.
grid = [[0] * 4 for _ in range(3)]

# Lỗi kinh điển: cách này tạo BA THAM CHIẾU TỚI CÙNG MỘT ROW, không phải ba row.
broken = [[0] * 4] * 3
broken[0][0] = 1
print(broken)              # [[1,0,0,0], [1,0,0,0], [1,0,0,0]]  <- cả ba đều đổi

Lỗi [[0] * 4] * 3 xuất hiện liên tục trong code thật. Toán tử * trên list copy tham chiếu, và [0] * 4 là một object list duy nhất được tham chiếu ba lần. Luôn dùng comprehension.

Slicing

Slice của Python tạo ra một list mới và copy các phần tử — a[i:j] tốn O(j − i) thời gian và O(j − i) bộ nhớ. Đây là cách vô tình tạo ra thuật toán bậc hai phổ biến nhất trong Python:

# O(n^2): mỗi lần slice copy toàn bộ phần đuôi còn lại
def dedupe_slow(items):
    out = []
    while items:
        out.append(items[0])
        items = items[1:]              # copy n-1, rồi n-2, rồi n-3 ... = O(n^2)
    return out

# O(n): dùng index, không bao giờ copy
def dedupe_fast(items):
    return [x for i, x in enumerate(items) if i == 0 or x != items[i - 1]]

Không phải ngôn ngữ nào cũng làm vậy. Slice của Go và của NumPy là view: chúng dùng chung khối bộ nhớ gốc và chỉ ghi lại offset, length, stride, nên slice là O(1) — nhưng ghi qua view sẽ sửa cả dữ liệu gốc. Cả hai thiết kế đều hợp lý; điều bạn cần biết là mình đang dùng cái nào.

import numpy as np

a = np.arange(10)
view = a[2:5]         # O(1) — không copy, dùng chung bộ nhớ
view[0] = 999
print(a[2])           # 999 — dữ liệu gốc đã thay đổi

b = list(range(10))
copy = b[2:5]         # O(3) — copy thật sự
copy[0] = 999
print(b[2])           # 2 — dữ liệu gốc không bị đụng tới

Array thực sự giỏi ở đâu

• Bất cứ thứ gì được index bằng một số nguyên nhỏ. Bucket của counting sort, bảng tần suất ký tự (counts = [0] * 26), bảng dynamic programming, adjacency matrix, direct-address table. Nếu không gian key nhỏ và dày đặc, array thắng hash table cả về tốc độ lẫn bộ nhớ.
• Dữ liệu đã sort + binary search. Tra cứu O(log n) với zero overhead pointer và locality hoàn hảo. Xem thuật toán tìm kiếm và module bisect của Python.
• Làm nền cho các cấu trúc khác. Binary heap (heap và priority queue) đặt một cây nhị phân đầy đủ vào một array với children(i) = 2i+1, 2i+2 và không cần pointer nào cả. Hash table (hash table) là array các bucket. Fenwick tree và segment tree cũng là array.
• Workload thiên về duyệt. Scan, filter, sum, transform. Không gì thắng nổi bộ nhớ liên tục ở đây.

Array thua ở đâu

• Chèn/xoá ở đầu trong vòng lặp. list.pop(0) và list.insert(0, x) là O(n); làm n lần là O(n²). Dùng collections.deque (xem stack và queue), vốn O(1) ở cả hai đầu.
• Chèn giữa liên tục khi đã giữ sẵn vị trí. Nếu bạn đã có con trỏ ngay tại điểm chèn, linked list nối vào trong O(1) còn array phải dịch O(n). Trong thực tế trường hợp này hiếm hơn sách giáo khoa ám chỉ, vì tìm ra vị trí ở linked list thường vẫn là O(n).
• Phần tử lớn với chi phí copy đắt. Resize copy mọi phần tử. Trong C++ đây là lý do việc tăng trưởng std::vector rẻ hơn nhiều với kiểu có move constructor noexcept; trong Python mọi thứ là pointer nên copy luôn là 8 byte mỗi phần tử.
• Dữ liệu thưa (sparse). Một array [0] * 1_000_000 để chứa 12 giá trị khác 0 lãng phí 8 MB. Hãy dùng dict hoặc một biểu diễn sparse.

Các kỹ thuật array thường gặp

Hai họ kỹ thuật xuất hiện liên tục và có note riêng ở hai con trỏ và cửa sổ trượt, nhưng đáng nhắc tên ở đây vì chúng chỉ hoạt động được nhờ index O(1):

# Prefix sum: tiền xử lý O(n) biến mọi truy vấn tổng đoạn thành O(1).
def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x            # prefix[k] = tổng của nums[:k]
    return prefix


def range_sum(prefix, lo, hi):                   # tổng của nums[lo:hi], O(1)
    return prefix[hi] - prefix[lo]


nums = [3, 1, 4, 1, 5, 9, 2, 6]
pre = build_prefix(nums)
print(range_sum(pre, 2, 6))                      # 4+1+5+9 = 19


# Đảo ngược tại chỗ với hai con trỏ: O(n) thời gian, O(1) bộ nhớ phụ.
def reverse_in_place(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1
    return arr


print(reverse_in_place([1, 2, 3, 4, 5]))         # [5, 4, 3, 2, 1]


# Xoá tại chỗ giữ nguyên thứ tự: một con trỏ ghi, một con trỏ đọc. O(n), không cấp phát.
def remove_value(arr, target):
    write = 0
    for read in range(len(arr)):
        if arr[read] != target:
            arr[write] = arr[read]
            write += 1
    del arr[write:]
    return arr


print(remove_value([3, 2, 3, 1, 3, 4], 3))       # [2, 1, 4]

Best Practices

• Cấp phát trước khi đã biết kích thước. [None] * n trong Python, make([]T, 0, n) trong Go, vec.reserve(n) trong C++. Nó loại bỏ mọi lần resize và toàn bộ chi phí copy đi kèm. Hiệu năng miễn phí chỉ với một dòng code.
• Không bao giờ pop(0) hay insert(0, x) trong vòng lặp. Đây là cách phổ biến nhất biến một thuật toán tuyến tính thành bậc hai trong Python. Dùng collections.deque cho FIFO, hoặc đảo ngược list rồi pop từ cuối.
• Không bao giờ dựng chuỗi hay list bằng cách slice/nối liên tục trong vòng lặp. s = s + chunk và items = items[1:] đều là O(n) mỗi vòng. Hãy gom vào một list rồi "".join(parts) ở cuối.
• Dùng [[x] * cols for _ in range(rows)], không bao giờ dùng [[x] * cols] * rows. Cách thứ hai lặp cùng một row rows lần và sẽ sinh ra một bug khiến bạn mất cả tiếng đồng hồ.
• Duyệt theo đúng thứ tự bộ nhớ với dữ liệu nhiều chiều. Row-major nghĩa là row ở vòng ngoài, column ở vòng trong. Trên ma trận lớn đây là chênh lệch 2–10× cho cùng một khối lượng công việc về mặt tiệm cận.
• Dùng NumPy khi array là số và lớn. Một list Python chứa một triệu int là một triệu pointer cộng một triệu object số nguyên đã đóng hộp — khoảng 36 MB so với 8 MB của NumPy, với locality tệ hơn nhiều và không có vectorization.
• Biết rõ index thực ra cần là cấu trúc gì. Nếu bạn thấy mình quét array để trả lời “x có tồn tại không”, thứ bạn cần là set hoặc hash table. Nếu cần dữ liệu đã sort và tìm kiếm, bạn cần bisect trên một array đã sort. Nếu luôn cần phần tử nhỏ nhất, bạn cần heap.
• Đừng thu nhỏ quá hăng. Nếu tự viết dynamic array, hãy dùng hysteresis — tăng khi đầy 100%, giảm khi còn 25% — nếu không việc dao động quanh ngưỡng sẽ khiến mọi thao tác thành O(n).
• Kiểm tra biên một cách có chủ đích. Python ném IndexError, nhưng index âm thì lặng lẽ vòng lại: a[-1] là phần tử cuối chứ không phải lỗi. Một index tính toán ra bị âm sẽ đọc nhầm phần tử thay vì báo lỗi rõ ràng.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Array data structure — Wikipedia
• Dynamic array — Wikipedia
• Amortized analysis — Wikipedia
• Row- and column-major order — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 17: Amortized Analysis
• Python Documentation — TimeComplexity of built-in types
• Python Documentation — array module
• NumPy Documentation — Internal memory layout of an ndarray
• Big-O Cheat Sheet
• VisuAlgo — Array and sorting visualisation

address(A[i]) = base_address + i * element_size

       index:     0        1        2        3        4
                +--------+--------+--------+--------+--------+
   memory:      |   17   |    3   |   99   |   42   |    8   |
                +--------+--------+--------+--------+--------+
     address:    0x1000   0x1004   0x1008   0x100C   0x1010
                    ^
                    base

   A[3]  ->  0x1000 + 3 * 4  =  0x100C   ->  42       O(1), one address computation

   DynamicArray:  size = 5,  capacity = 8

                +----+----+----+----+----+----+----+----+
     _data ---> | 17 |  3 | 99 | 42 |  8 |    |    |    |
                +----+----+----+----+----+----+----+----+
                  0    1    2    3    4    ^^^^^^^^^^^^
                                            slack: allocated but unused

   append(23):  size < capacity, so just write and increment  ->  O(1)
   append(...) when size == capacity:
        allocate a new block of capacity*2, copy all n elements, free the old  ->  O(n)

import ctypes


class DynamicArray:
    """A dynamic array built on a fixed-capacity raw array, with manual doubling."""

    GROWTH_FACTOR = 2

    def __init__(self):
        self._n = 0                                # number of elements actually stored
        self._capacity = 1                         # slots allocated
        self._data = self._make_array(self._capacity)

    @staticmethod
    def _make_array(capacity):
        """Allocate a raw, fixed-size block of `capacity` slots. Cannot grow."""
        return (capacity * ctypes.py_object)()

    def __len__(self):
        return self._n

    def __getitem__(self, i):
        if not 0 <= i < self._n:                   # negative indices omitted for clarity
            raise IndexError("index out of range")
        return self._data[i]                       # O(1) — address arithmetic

    def __setitem__(self, i, value):
        if not 0 <= i < self._n:
            raise IndexError("index out of range")
        self._data[i] = value                      # O(1)

    def append(self, value):
        """Amortized O(1): O(1) most of the time, O(n) on the resize."""
        if self._n == self._capacity:              # full — no slack left
            self._resize(self._capacity * self.GROWTH_FACTOR)
        self._data[self._n] = value
        self._n += 1

    def _resize(self, new_capacity):
        """O(n): allocate a bigger block and copy every element into it."""
        new_data = self._make_array(new_capacity)
        for i in range(self._n):                   # the copy is what costs O(n)
            new_data[i] = self._data[i]
        self._data = new_data                      # old block becomes garbage
        self._capacity = new_capacity

    def insert(self, i, value):
        """O(n): every element from index i onward shifts one slot right."""
        if not 0 <= i <= self._n:
            raise IndexError("index out of range")
        if self._n == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)
        for j in range(self._n, i, -1):            # walk backwards to avoid overwriting
            self._data[j] = self._data[j - 1]
        self._data[i] = value
        self._n += 1

    def pop(self, i=None):
        """O(1) at the end, O(n) anywhere else — the tail must close the gap."""
        if self._n == 0:
            raise IndexError("pop from empty array")
        if i is None:
            i = self._n - 1
        if not 0 <= i < self._n:
            raise IndexError("index out of range")
        value = self._data[i]
        for j in range(i, self._n - 1):            # shift the tail left
            self._data[j] = self._data[j + 1]
        self._n -= 1
        # Shrink at 1/4 full, not 1/2 — see "hysteresis" below
        if 0 < self._n <= self._capacity // 4:
            self._resize(max(1, self._capacity // 2))
        return value

    def __iter__(self):
        for i in range(self._n):
            yield self._data[i]

    def __repr__(self):
        return f"DynamicArray({list(self)}, capacity={self._capacity})"


arr = DynamicArray()
for x in [17, 3, 99, 42, 8]:
    arr.append(x)
print(arr)              # DynamicArray([17, 3, 99, 42, 8], capacity=8)
arr.insert(2, 55)
print(arr)              # DynamicArray([17, 3, 55, 99, 42, 8], capacity=8)
print(arr.pop(0), arr)  # 17 DynamicArray([3, 55, 99, 42, 8], capacity=8)

1 + 2 + 4 + 8 + ... + n/2 + n  <  2n

   Sequential scan of an int array (64-byte cache line, 4-byte ints):

   miss  hit hit hit ... hit   miss  hit hit hit ... hit
   [ A[0] A[1] ... A[15] ]     [ A[16] ... A[31] ]
   \____ one cache line ___/   \____ one cache line __/

   -> 1 memory fetch per 16 elements, plus the prefetcher sees the stride
      and loads the next line before you ask for it.

   Linked list traversal:

   node ---> ??? ---> ??? ---> ???      each `next` is an unpredictable address
   miss      miss     miss     miss     -> no prefetch, ~1 memory fetch per element

import time

n = 20_000_000
data = list(range(n))
index = list(range(n))

start = time.perf_counter()
total = 0
for i in index:                      # sequential: perfect locality
    total += data[i]
sequential = time.perf_counter() - start

import random
random.shuffle(index)
start = time.perf_counter()
total = 0
for i in index:                      # same operations, random address order
    total += data[i]
shuffled = time.perf_counter() - start

print(f"sequential {sequential:.2f}s vs shuffled {shuffled:.2f}s")
# Typically 3-10x slower shuffled, for identical O(n) work.

   Logical 3x4 matrix:

        col:  0   1   2   3
   row 0:   [ a   b   c   d ]
   row 1:   [ e   f   g   h ]
   row 2:   [ i   j   k   l ]

   Row-major layout (C, C++, Python/NumPy default, Java):
   [ a b c d | e f g h | i j k l ]
     M[r][c] = flat[r * COLS + c]

   Column-major layout (Fortran, MATLAB, R, BLAS internals):
   [ a e i | b f j | c g k | d h l ]
     M[r][c] = flat[c * ROWS + r]

def flat_matrix(rows, cols, fill=0):
    """A true 2D array: one contiguous block, row-major indexing."""
    return {"rows": rows, "cols": cols, "data": [fill] * (rows * cols)}


def get(m, r, c):
    return m["data"][r * m["cols"] + c]          # the index formula, O(1)


def set_(m, r, c, value):
    m["data"][r * m["cols"] + c] = value


m = flat_matrix(3, 4)
set_(m, 1, 2, 99)
print(get(m, 1, 2))        # 99
print(m["data"])           # [0,0,0,0, 0,0,99,0, 0,0,0,0] — the row-major block


# Python's usual "2D array" is a list of lists — NOT contiguous.
# Each row is a separate heap allocation; the outer list holds pointers to them.
grid = [[0] * 4 for _ in range(3)]

# The classic bug: this makes THREE REFERENCES TO THE SAME ROW, not three rows.
broken = [[0] * 4] * 3
broken[0][0] = 1
print(broken)              # [[1,0,0,0], [1,0,0,0], [1,0,0,0]]  <- all three changed

# O(n^2): each slice copies the remaining tail
def dedupe_slow(items):
    out = []
    while items:
        out.append(items[0])
        items = items[1:]              # copies n-1, then n-2, then n-3 ... = O(n^2)
    return out

# O(n): index, never copy
def dedupe_fast(items):
    return [x for i, x in enumerate(items) if i == 0 or x != items[i - 1]]

import numpy as np

a = np.arange(10)
view = a[2:5]         # O(1) — no copy, shares memory
view[0] = 999
print(a[2])           # 999 — the original changed

b = list(range(10))
copy = b[2:5]         # O(3) — a real copy
copy[0] = 999
print(b[2])           # 2 — the original is untouched

# Prefix sums: O(n) preprocessing turns any range-sum query into O(1).
def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x            # prefix[k] = sum of nums[:k]
    return prefix


def range_sum(prefix, lo, hi):                   # sum of nums[lo:hi], O(1)
    return prefix[hi] - prefix[lo]


nums = [3, 1, 4, 1, 5, 9, 2, 6]
pre = build_prefix(nums)
print(range_sum(pre, 2, 6))                      # 4+1+5+9 = 19


# In-place reversal with two pointers: O(n) time, O(1) extra space.
def reverse_in_place(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1
    return arr


print(reverse_in_place([1, 2, 3, 4, 5]))         # [5, 4, 3, 2, 1]


# Stable in-place removal: one write pointer, one read pointer. O(n), no allocation.
def remove_value(arr, target):
    write = 0
    for read in range(len(arr)):
        if arr[read] != target:
            arr[write] = arr[read]
            write += 1
    del arr[write:]
    return arr


print(remove_value([3, 2, 3, 1, 3, 4], 3))       # [2, 1, 4]