Array — trực quan các thao tác
1. Truy cập theo chỉ số: O(1)
2. Chèn / xóa giữa: O(n) — phải dịch chuyển
3. Binary search: O(log n)
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
4. Đả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
5. 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).
Thử: append liên tục — copy chỉ xảy ra tại các mốc 2^k; chia tổng công cho n phép append: trung bình O(1).
size=0 · capacity=1
6. 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ờ.