Chương 17. Kỹ thuật lập trình nâng cao
Độ phức tạp thuật toán
Phần tiêu đề “Độ phức tạp thuật toán”Để biết chương trình có chạy kịp không, ta đếm số phép tính theo kích thước dữ liệu n, bỏ qua hằng số, và viết bằng ký hiệu O lớn:
| Độ phức tạp | Ví dụ | n lớn nhất chạy kịp 1 giây (Python) |
|---|---|---|
| O(1) | công thức, truy cập a[i], tra từ điển | mọi n |
| O(log n) | tìm kiếm nhị phân, lũy thừa nhanh | mọi n |
| O() | kiểm tra số nguyên tố | khoảng 1013 |
| O(n) | một vòng lặp qua dãy | khoảng 106 đến 107 |
| O(n log n) | sắp xếp sort | khoảng 106 |
| O(n2) | hai vòng lặp lồng nhau | khoảng 3 × 103 |
| O(2n) | duyệt mọi tập con | khoảng 20 |
| O(n!) | duyệt mọi hoán vị | khoảng 9 |
Python thực hiện được khoảng 107 phép tính đơn giản mỗi giây, chậm hơn C++ khoảng 10 đến 50 lần. Vì vậy với Python, chọn thuật toán đúng độ phức tạp càng quan trọng: thuật toán O(n2) với n = 105 cần 1010 phép tính, không ngôn ngữ nào chạy kịp; nhưng O(n log n) thì Python làm được trong khoảng nửa giây.
Các hàm có sẵn của Python (sum, sorted, max, str.join, các thao tác trên set, dict) viết bằng
C, chạy nhanh hơn nhiều lần so với vòng lặp tự viết làm cùng việc. Dùng chúng khi có thể.
Đọc ghi nhanh
Phần tiêu đề “Đọc ghi nhanh”input() và print() khá chậm khi gọi hàng trăm nghìn lần. Ba kỹ thuật hay dùng:
- Đọc toàn bộ một lần:
data = sys.stdin.buffer.read().split()cho danh sách mọi “từ” của dữ liệu vào (dạngbytes,int()đổi được trực tiếp), rồi lấy dần bằng một chỉ số. - Đọc từng dòng nhanh:
input = sys.stdin.readline(dòng đọc được giữ\nở cuối). - In một lần: gom kết quả vào danh sách, cuối cùng in
"\n".join(...)(hoặcsys.stdout.write(...)) thay vì gọiprintcho từng dòng.
import sys
def main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) a = list(map(int, data[2:2 + n])) pos = 2 + n # vị trí của số tiếp theo cần đọc answers = [] for _ in range(q): left, right = int(data[pos]), int(data[pos + 1]) pos += 2 answers.append(max(a[left - 1:right])) sys.stdout.write("\n".join(map(str, answers)) + "\n")
main()88-2Một mẹo nữa đã gặp ở chương 8: đặt phần chính trong hàm main(). Trong hàm, Python truy cập biến cục
bộ nhanh hơn biến toàn cục, và phép ghép xâu += không bị chậm.
Mảng cộng dồn
Phần tiêu đề “Mảng cộng dồn”Bài toán: cho dãy n số và q câu hỏi “tổng các số từ vị trí l đến r là bao nhiêu?”. Cộng trực tiếp mỗi câu hỏi mất O(n), tổng cộng O(n × q) = 1010 với n = q = 105.
Ý tưởng: tính trước prefix[i] là tổng i số đầu tiên (prefix[0] = 0). Khi đó tổng đoạn [l, r]
(đánh số từ 1) bằng prefix[r] - prefix[l - 1]: lấy tổng r số đầu trừ đi tổng l − 1 số đầu.
from itertools import accumulate
a = [3, -1, 4, 1, 5, 9]prefix = [0] * (len(a) + 1)for i in range(1, len(a) + 1): prefix[i] = prefix[i - 1] + a[i - 1]print(prefix)print(prefix[4] - prefix[1]) # a2 + a3 + a4 = -1 + 4 + 1print([0] + list(accumulate(a))) # cách viết ngắn[0, 3, 2, 6, 7, 12, 21]4[0, 3, 2, 6, 7, 12, 21]Tính mảng cộng dồn mất O(n), mỗi câu hỏi O(1), tổng cộng O(n + q). Hàm accumulate của module
itertools tính dãy tổng dồn, chạy nhanh hơn vòng lặp tự viết.
Mảng hiệu: cộng một giá trị vào cả đoạn
Phần tiêu đề “Mảng hiệu: cộng một giá trị vào cả đoạn”Bài toán ngược: q thao tác “cộng v vào mọi phần tử từ l đến r”, cuối cùng in dãy. Cộng trực tiếp mỗi thao tác mất O(n).
Ý tưởng: ghi lại “từ vị trí l bắt đầu cộng v” và “từ vị trí r + 1 thôi cộng v” vào mảng hiệu diff:
diff[l] += v, diff[r + 1] -= v. Sau mọi thao tác, cộng dồn diff từ trái sang phải được lượng cần
cộng vào từng vị trí.
n = 6a = [0] * ndiff = [0] * (n + 1)for left, right, value in [(2, 4, 5), (3, 6, 1)]: # vị trí đánh số từ 1 diff[left - 1] += value diff[right] -= valueadded = 0for i in range(n): added += diff[i] a[i] += addedprint(a)[0, 5, 6, 6, 1, 1]Mỗi thao tác O(1), cuối cùng một lần cộng dồn O(n).
Sàng Eratosthenes
Phần tiêu đề “Sàng Eratosthenes”Kiểm tra từng số từ 1 đến N có phải số nguyên tố không bằng cách thử ước tới √ mất O(N). Sàng Eratosthenes làm nhanh hơn nhiều: viết các số từ 2 đến N; lấy số nhỏ nhất chưa bị gạch (là số nguyên tố p), gạch mọi bội của p; lặp lại.
def sieve(limit): """Danh sách is_prime với is_prime[k] = True khi k là số nguyên tố, k từ 0 đến limit.""" is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False p = 2 while p * p <= limit: if is_prime[p]: for multiple in range(p * p, limit + 1, p): # bắt đầu từ p * p is_prime[multiple] = False p += 1 return is_prime
is_prime = sieve(50)print([k for k in range(51) if is_prime[k]])[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]Hai điểm cần hiểu:
- Bắt đầu gạch từ p × p: các bội nhỏ hơn như 2p, 3p đã bị gạch bởi các số nguyên tố nhỏ hơn p.
- Chỉ cần p × p ≤ N: một hợp số k ≤ N có ước nguyên tố không vượt quá ≤ , nên đã bị gạch.
Độ phức tạp khoảng O(N log log N), gần như O(N). Với N = 106, hàm trên chạy khoảng 0,1 giây. Có thể
nhanh hơn nữa bằng cách gạch cả một lát cắt trong một lệnh:
is_prime[p * p::p] = bytearray(len(range(p * p, limit + 1, p))) với is_prime là bytearray
(xem lời giải bài SANGNT).
Kết hợp với mảng cộng dồn: count[k] là số số nguyên tố không vượt quá k, thì số số nguyên tố trong
đoạn [l, r] là count[r] - count[l - 1].
Tìm kiếm nhị phân
Phần tiêu đề “Tìm kiếm nhị phân”Trên dãy đã sắp xếp
Phần tiêu đề “Trên dãy đã sắp xếp”Tìm x trong dãy đã sắp xếp: so x với phần tử giữa; nhỏ hơn thì chỉ cần tìm ở nửa trái, lớn hơn thì nửa phải. Mỗi bước loại một nửa, nên dãy 106 phần tử chỉ cần khoảng 20 bước: O(log n).
Module bisect có sẵn hai hàm:
| Hàm | Trả về |
|---|---|
bisect_left(a, x) | vị trí đầu tiên có a[i] >= x (số phần tử nhỏ hơn x) |
bisect_right(a, x) | vị trí đầu tiên có a[i] > x (số phần tử nhỏ hơn hoặc bằng x) |
from bisect import bisect_left, bisect_right
a = [1, 3, 3, 5, 8, 13]print(bisect_left(a, 3), bisect_right(a, 3)) # vị trí của các số 3: từ 1 đến trước 3print(bisect_right(a, 3) - bisect_left(a, 3)) # số lần xuất hiện của 3print(bisect_right(a, 6)) # số phần tử <= 6print(bisect_left(a, 4) < len(a) and a[bisect_left(a, 4)] == 4) # 4 có trong dãy?1 324FalseTự viết tìm kiếm nhị phân (tìm vị trí đầu tiên có a[i] >= x):
def lower_bound(a, x): low, high = 0, len(a) # đáp số nằm trong đoạn [low, high] while low < high: middle = (low + high) // 2 if a[middle] >= x: high = middle # middle có thể là đáp số else: low = middle + 1 # đáp số nằm sau middle return low
print(lower_bound([1, 3, 3, 5, 8, 13], 4), lower_bound([1, 3, 3, 5, 8, 13], 100))3 6Tìm kiếm nhị phân trên kết quả
Phần tiêu đề “Tìm kiếm nhị phân trên kết quả”Nhiều bài hỏi “giá trị lớn nhất (hoặc nhỏ nhất) thỏa mãn điều kiện”. Nếu điều kiện có tính đơn điệu (giá trị L thỏa mãn thì mọi giá trị nhỏ hơn L cũng thỏa mãn), ta tìm kiếm nhị phân trên chính đáp số: thử giá trị giữa, thỏa mãn thì đáp số ở nửa trên, không thì ở nửa dưới.
Ví dụ: tìm số nguyên lớn nhất L có L2 ≤ N (căn bậc hai nguyên của N), không dùng math.isqrt:
def integer_sqrt(n): low, high = 0, n # L = low thỏa mãn; mọi L > high không thỏa mãn while low < high: middle = (low + high + 1) // 2 # làm tròn lên để vòng lặp luôn tiến if middle * middle <= n: low = middle else: high = middle - 1 return low
print(integer_sqrt(17), integer_sqrt(10**18), integer_sqrt(0))4 1000000000 0Chú ý middle = (low + high + 1) // 2 (làm tròn lên): khi high = low + 1, làm tròn xuống sẽ cho
middle = low, nhánh low = middle không làm thay đổi gì và vòng lặp chạy mãi.
Hai con trỏ
Phần tiêu đề “Hai con trỏ”Với dãy số dương, tìm đoạn liên tiếp dài nhất có tổng không vượt quá S. Thử mọi đoạn mất O(n2). Kỹ
thuật hai con trỏ: con trỏ phải right lần lượt mở rộng đoạn; mỗi khi tổng vượt S thì con trỏ trái
left tiến lên để thu hẹp. Vì các số dương, khi right tăng thì left không bao giờ phải lùi lại.
a = [2, 1, 3, 1, 1, 4, 2]limit = 6left = 0window_sum = 0best = 0for right in range(len(a)): window_sum += a[right] while window_sum > limit: window_sum -= a[left] left += 1 best = max(best, right - left + 1)print(best)4Mỗi con trỏ chỉ tiến, mỗi con trỏ đi tối đa n bước, nên tổng cộng O(n) dù có vòng while lồng trong
vòng for. Đoạn tìm được là 1, 3, 1, 1 (tổng 6).
Tóm tắt
Phần tiêu đề “Tóm tắt”- Đếm độ phức tạp trước khi viết code; Python khoảng 107 phép tính mỗi giây.
- Đọc nhanh
sys.stdin.buffer.read().split(), in một lần bằng"\n".join(...); phần chính trongmain(). - Mảng cộng dồn: tổng đoạn [l, r] là
prefix[r] - prefix[l - 1]. Mảng hiệu:diff[l] += v,diff[r + 1] -= v. - Sàng Eratosthenes: gạch bội của p từ p × p, chỉ cần p × p ≤ N.
bisect_left,bisect_righttrên dãy đã sắp xếp; tìm kiếm nhị phân trên kết quả khi điều kiện đơn điệu.- Hai con trỏ trên dãy dương: O(n).
Bài tập thực hành
Phần tiêu đề “Bài tập thực hành”Chương này có 6 bài tập thực hành:
- Bài 17.1. Tổng đoạn
- Bài 17.2. Đếm số nhỏ hơn hoặc bằng
- Bài 17.3. Số nguyên tố trong đoạn
- Bài 17.4. Cộng trên đoạn
- Bài 17.5. Đoạn con dài nhất
- Bài 17.6. Cắt gỗ
Mua bộ tài liệu đầy đủ
Phần tiêu đề “Mua bộ tài liệu đầy đủ”Đề bài chi tiết (có ví dụ), lời giải từng bài (ý tưởng, các bước, lỗi hay gặp) kèm code Python, bộ test chấm tự động bằng Themis và bài giảng PowerPoint của chương này có trong bộ giáo trình Python đầy đủ.
Thầy cô và các em muốn mua bộ tài liệu đầy đủ vui lòng liên hệ tác giả Th.S Trần Huy Phúc:
- Zalo: 0972465159
- Facebook: facebook.com/tran.huyphuc.3