1. Mô Tả Vấn Đề
Cho một số nguyên không âm n, hãy tạo mảng ans có độ dài n+1 sao cho:
ans[i] = số lượng bit 1 trong biểu diễn nhị phân của số i, với 0 ≤ i ≤ n. 2. Các Phương Pháp và Triển khai
2.1 Phương Pháp Thô (Native)
def countBits_native(self, n: int) -> List[int]: ans = [] for i in range(n+1): ans.append(bin(i).count('1')) return ans - Ý tưởng: Với mỗi i, chuyển sang chuỗi nhị phân bằng
bin(i)rồi đếm ký tự'1'. - Độ phức tạp thời gian: O(nlogn) vì mỗi
bin(i)và.count('1')tốn O(logi), tổng cộng ~∑i=0 → n: O(logi)= O(n \log n). - Độ phức tạp không gian: O(n)
2.2 Quy Hoạch Động (DP)
def countBits_dp(self, n: int) -> List[int]: ans = [0] * (n+1) for i in range(1, n+1): ans[i] = ans[i // 2] + (i % 2) return ans - Ý tưởng: Đối với mỗi số i, mối quan hệ giữa i và i /2:
- Nếu i là số chẵn khi đó i và i/2 cùng số lượng 1 trong biểu diễn nhị phân
- Nếu i lẻ thì biểu diễn nhị phân của i và i/2 sẽ cách nhau 1 số 1 ( least significant bit)
- Độ phức tạp thời gian: O(n), mỗi i tính trong thời gian O(1).
- Độ phức tạp không gian: O(n)
2.3 Đệ Quy
def countBits_recursive(self, n: int) -> List[int]: ans = [0] * (n+1) def count_ones(num): if num == 0: return 0 if ans[num] != 0: return ans[num] ans[num] = count_ones(num//2) + (num & 1) return ans[num] for i in range(1, n+1): count_ones(i) return ans - Ý tưởng: Sử dụng đệ quy với bộ nhớ, áp dụng cùng công thức như DP.
- Độ phức tạp thời gian: O(n) trung bình, mỗi số chỉ tính một lần.
- Độ phức tạp không gian: O(n+logn), trong đó O(n) cho mảng và O(log n) cho độ sâu đệ quy.
- Lưu ý: Có overhead của đệ quy, không thực sự tối ưu bằng DP vòng lặp.
3. Tổng Kết Độ Phức Tạp
| Phương pháp | Thời gian | Không gian |
|---|---|---|
| Native (bin + count) | O(n log n) | O(n) |
| DP (dich bit + cong) | O(n) | O(n) |
| Đệ quy + Memo | O(n) trung bình | O(n + log n) (stack) |
4. Đánh Giá và Khuyến Nghị
- Native: Dễ hiểu, nhưng chậm khi n lớn. Phù hợp kịch bản nhỏ hoặc minh họa.
- DP: Tối ưu nhất về thời gian và không gian. Lựa chọn hàng đầu cho dữ liệu lớn.
- Đệ quy: Minh họa công thức đệ quy rõ ràng, nhưng overhead và rủi ro tràn stack.