Array — trực quan các thao tác

Truy cập theo chỉ số: O(1)

Chỉ số:

Chèn / xóa giữa: O(n) — phải dịch chuyển

Vị trí: Giá trị:

Binary search: O(log n)

Tìm:

function binarySearch(arr, target):
    lo, hi = 0, len(arr)-1
    while lo <= hi:
        mid = (lo + hi) / 2
        if arr[mid] == target: return mid
        if arr[mid] < target:  lo = mid + 1
        else:                  hi = mid - 1
    return -1

Đảo ngược mảng tại chỗ — two pointer: O(n)

function reverse(arr):
    left, right = 0, len(arr)-1
    while left < right:
        swap(arr[left], arr[right])
        left += 1
        right -= 1

Dynamic array — resize doubling (vì sao amortized O(1)?)

Khi size == capacity, cấp mảng mới gấp đôi và copy toàn bộ → lần đó tốn O(n). Nhưng tổng cost của n lần push = O(n), nên trung bình mỗi lần = O(1).

size=0 · capacity=1

Sliding window: tổng lớn nhất cửa sổ k (README §8.3)

Trượt cửa sổ size k: mỗi bước thêm phần tử phải, bỏ phần tử trái → cập nhật tổng O(1) thay vì cộng lại cả cửa sổ. Tím = cửa sổ hiện tại, viền vàng = cửa sổ tổng lớn nhất tới giờ.

k =