Không phải ba vòng đều chạy n lượt
```python
def dem_ba_vong(n):
r = 0
for i in range(n - 1):
for j in range(i + 1, n):
for k in range(1, j):
r += 1
return r
```
Thân trong chỉ tăng `r`, nên giá trị trả về **bằng số lần thân trong chạy**. Với `n = 4`: khi `j = 1`, vòng `k` chạy 0 lượt và có 1 giá trị `i`; `j = 2` có 1 lượt `k` và 2 giá trị `i`; `j = 3` có 2 lượt `k` và 3 giá trị `i`. Tổng là `0×1 + 1×2 + 2×3 = 8`.
Gom theo chỉ số j để thấy bậc
Với mỗi `j` từ 1 đến `n−1`, có `j` cách chọn `i < j` và `j−1` giá trị `k`. Vì thế `r = Σ j(j−1)` với `j = 1, …, n−1`; rút gọn được `n(n−1)(n−2)/3`. Khi `n` lớn, hạng bậc ba chi phối, nên mã có bậc `O(n³)`. Với `n = 0, 1` hoặc `2`, thân trong không chạy và hàm trả 0. Đếm lượt theo giới hạn thật giúp tránh nhầm rằng ba vòng đều chạy chính xác `n³` lượt.
Bài luyện
Theo mã trong bài, `dem_ba_vong(4)` trả giá trị nào?
Còn thiếu các lượt theo j=3.
2+6=8, không phải 6.
0×1 + 1×2 + 2×3 = 8.
4³ không phải số lượt chính xác của ba vòng này.
Lời giải
Gom theo j=1,2,3 cho 0,2,6 lần tăng r; tổng là 8.
Bài luyện
Với một giá trị `j` cố định, có bao nhiêu cặp lựa chọn `i` và `k` cho thân trong?
Chỉ đếm giá trị k.
Chỉ đếm giá trị i.
Có j giá trị i và j−1 giá trị k.
n³ là bậc, không phải số cặp tại j cố định.
Lời giải
Với j cố định, i có j khả năng (0 đến j−1) và k có j−1 khả năng (1 đến j−1), nên tích là j(j−1).
Bài luyện
Từ `r = n(n−1)(n−2)/3`, bậc tăng của hàm khi `n` lớn là gì?
r tăng theo n.
Tích ba thừa số cùng cỡ n.
Còn thiếu một thừa số n.
Hạng cao nhất là n³/3.
Lời giải
Khai triển tích có hạng cao nhất n³/3, nên bậc O(n³).
Đang học