Bài 25. Độ phức tạp của thuật toán
Bài học này giới thiệu vì sao cùng một bài toán có thể có nhiều thuật toán khác nhau, và làm thế nào để đo một cách khách quan xem thuật toán nào hiệu quả hơn - đặc biệt khi phải xử lí dữ liệu rất lớn - thông qua khái niệm độ phức tạp thuật toán và các kí hiệu quen thuộc như O(1), O(log n), O(n), O(n^2).
- Cánh DiềuTin học 11 (Khoa học máy tính) - Chủ đề F(CS) · Bài 5. Đánh giá thuật toántr. 107
- Kết nối tri thứcTin học 11 (Khoa học máy tính) - Bài 24. Đánh giá độ phức tạp thời gian thuật toántr. 111–114
- Kết nối tri thứcTin học 11 (Khoa học máy tính) - Bài 25. Thực hành xác định độ phức tạp thời gian thuật toántr. 115–117
Bắt đầu bằng một hình dung
Hãy tưởng tượng bạn cần tìm số điện thoại của một người trong một cuốn danh bạ giấy. Nếu cuốn danh bạ chỉ có 10 người, cách đơn giản nhất - lật lần lượt từng trang, đọc từng tên một cho tới khi gặp đúng tên cần tìm - vẫn hoàn toàn ổn: cùng lắm chỉ mất vài giây, dù tên đó nằm ở trang cuối cùng.
Nhưng nếu đó là danh bạ của cả một thành phố, với một triệu người, cách ‘đọc từng tên một’ đó sẽ trở thành một cơn ác mộng - trong tình huống xấu nhất, bạn phải lật qua gần hết một triệu cái tên mới tìm ra người cần tìm. Trong khi đó, nếu cuốn danh bạ đã được sắp xếp theo thứ tự bảng chữ cái (như hầu hết danh bạ thật), bạn có thể mở ngay vào khoảng giữa cuốn sách, so sánh tên ở đó với tên cần tìm để biết nên tìm tiếp ở nửa trước hay nửa sau, rồi lặp lại cách thu hẹp một nửa như vậy - chỉ khoảng 20 bước là tìm ra, dù danh bạ có cả triệu người.
Hai cách làm trên đều cho ra đúng kết quả. Nhưng rõ ràng có một cách ‘chịu đựng được’ dữ liệu lớn, còn cách kia thì không. Làm sao để so sánh các thuật toán một cách khách quan, thay vì chỉ nói chung chung rằng ‘thuật toán này có vẻ nhanh hơn’?
Nội dung bài học
- Một bài toán, nhiều thuật toán khác nhau
- Đo hiệu quả bằng gì? Đếm phép tính, không bấm giờ
- Kí hiệu O - cách viết gọn độ phức tạp
- So sánh trực quan: n tăng gấp 10 lần thì sao?
Tóm tắt lý thuyết cần nhớ
- Cùng một bài toán có thể giải bằng nhiều thuật toán khác nhau; để biết thuật toán nào hiệu quả hơn - nhất là khi dữ liệu lớn - cần một cách đo khách quan, không phụ thuộc vào máy tính đang chạy.
- Cách đo đó là đếm số phép tính cơ bản (so sánh, phép gán...) mà thuật toán thực hiện, tính theo kích thước dữ liệu
n, và quan tâm đến xu hướng tăng của nó khinrất lớn. - Bốn mức độ phức tạp thường gặp, từ nhanh đến chậm:
O(1)(không đổi),O(log n)(rất nhanh, như tìm kiếm nhị phân),O(n)(tuyến tính, như tìm kiếm tuần tự),O(n^2)(chậm, như sắp xếp nổi bọt). - Khi
ntăng gấp 10 lần,O(n)tăng gấp 10 nhưngO(n^2)tăng gấp 100 - nên thuật toánO(n^2)vẫn ổn với dữ liệu nhỏ nhưng nhanh chóng trở nên rất chậm với dữ liệu lớn; chọn thuật toán phù hợp vì vậy rất quan trọng.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| Big-O | bích-ô | độ phức tạp (kí hiệu O lớn) Cách ước lượng chương trình chạy nhanh hay chậm khi dữ liệu to lên - càng 'O lớn' thì càng lâu. |
| algorithm | AL-gô-rít-thầm | thuật toán Các bước làm một việc theo đúng thứ tự để ra kết quả - như công thức pha mì gói: đổ nước sôi, chờ 3 phút, rồi ăn. |
| loop | lúp | vòng lặp Bảo máy làm lại một việc nhiều lần - giống em chạy nhiều vòng quanh sân trường. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 26 câu, chấm điểm tự động và giải thích từng câu sai.
- Vì đồng hồ chỉ đo được thời gian tính bằng phút, không đo được giây
- Vì thời gian chạy còn phụ thuộc vào tốc độ máy tính, không phản ánh đúng bản chất thuật toán
- Vì các ngôn ngữ lập trình không cho phép đo thời gian chạy chương trình
- Vì bấm giờ chỉ áp dụng được cho những chương trình có vòng lặp
n thường dùng để chỉ điều gì?- Số lượng thuật toán có thể dùng để giải một bài toán
- Kích thước (số lượng phần tử) của dữ liệu đầu vào
- Số lần chương trình bị lỗi khi chạy thử
- Tốc độ xử lí của bộ vi xử lí (CPU)
n biểu diễn kích thước của dữ liệu đầu vào - ví dụ số phần tử trong một danh sách cần tìm kiếm hoặc cần sắp xếp. Độ phức tạp thuật toán mô tả số phép tính cần thực hiện thay đổi thế nào khi n thay đổi.- O(1)
- O(log n)
- O(n)
- O(n^2)
- a)Độ phức tạp O(1) nghĩa là số phép tính của thuật toán luôn không đổi, không phụ thuộc vào kích thước dữ liệu n.Đúng
- b)Thuật toán có độ phức tạp O(n^2) luôn chạy chậm hơn thuật toán có độ phức tạp O(n), trong mọi trường hợp, với mọi kích thước dữ liệu.Sai
- c)Kí hiệu O trong độ phức tạp thuật toán mô tả xu hướng tăng của số phép tính khi kích thước dữ liệu tăng lên, không phải là số giây chính xác mà chương trình chạy.Đúng
- d)Tìm kiếm nhị phân có thể áp dụng cho bất kỳ danh sách nào, kể cả danh sách chưa được sắp xếp, mà vẫn cho kết quả đúng.Sai
- (a) Đúng - đây chính là định nghĩa của O(1): số phép tính cố định, không phụ thuộc n.
- (b) Sai - độ phức tạp mô tả xu hướng khi n rất lớn; với dữ liệu nhỏ, một thuật toán O(n^2) đơn giản vẫn có thể chạy tốt, thậm chí nhanh hơn một thuật toán khác về mặt thực tế.
- (c) Đúng - kí hiệu O mô tả tốc độ tăng của số phép tính theo n, không phải số giây cụ thể, vì thời gian thực tế còn phụ thuộc vào tốc độ máy tính.
- (d) Sai - tìm kiếm nhị phân chỉ cho kết quả đúng khi danh sách đã được sắp xếp trước; nếu danh sách chưa sắp xếp, việc thu hẹp một nửa phạm vi tìm kiếm không còn ý nghĩa và có thể bỏ sót giá trị cần tìm.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 26 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.