Nối tiếp thì cộng; lồng nhau thì nhân
Nếu một đoạn duyệt `n` phần tử rồi một đoạn khác dùng hai vòng `n` lượt lồng nhau, tổng số lượt chính là `n + n²`. Khi `n` lớn, `n²` chi phối, nên bậc là `O(n²)`. Nếu hai vòng mỗi vòng `n` lượt lồng nhau, thân trong chạy `n × n` lượt, cũng là `O(n²)`. Hệ số cố định không đổi bậc: `3n²` vẫn là `O(n²)`. Quy tắc này giả định các bước trong thân vòng là thao tác có chi phí không tăng theo `n`.
Nhân đôi cho số lượt logarit
Một vòng bắt đầu từ 1, mỗi lượt nhân đôi và dừng khi đạt `n`:
```python
def dem_nhan_doi(n):
i = 1
so_luot = 0
while i < n:
i *= 2
so_luot += 1
return so_luot
```
Với `n = 16`, giá trị `i` lần lượt là 1 → 2 → 4 → 8 → 16, nên thân vòng chạy **4 lần**. Mỗi lượt nhân đôi, vì vậy khi `n` tăng rất lớn, số lượt tăng theo `log₂ n`, được viết `O(log n)`. Với `n ≤ 1`, vòng không chạy; bậc O lớn xét khi `n` đủ lớn.
Bài luyện
Một đoạn có `n` lượt, rồi đến đoạn khác có `n²` lượt. Bậc của tổng số lượt là gì?
Tổng tăng theo n.
n² chi phối n.
n + n² có bậc n².
Không có phép nhân thêm n.
Lời giải
Hai đoạn nối tiếp có n + n² lượt; giữ hạng tăng nhanh hơn được O(n²).
Bài luyện
Với `dem_nhan_doi(16)`, thân vòng lặp chạy mấy lần?
Còn thiếu lượt 8→16.
Các lượt là 1→2, 2→4, 4→8, 8→16.
Không tăng từng đơn vị.
16 là mốc dừng, không phải số lượt.
Lời giải
Từ 1 phải nhân đôi bốn lần để đạt 16; sau đó điều kiện i < n sai.
Bài luyện
Nếu thân trong mất `n` lượt và thân ngoài cũng có `n` lượt, tổng số lượt thân trong là gì?
Hai vòng lồng nhau nhân số lượt.
Mỗi trong n lượt ngoài có n lượt trong.
Không phải một lượt thêm.
Không có thao tác chia/nhân đôi.
Lời giải
n lượt ngoài × n lượt trong mỗi lần = n² lượt thân trong.
Đang học