1. Các khái niệm cơ bản
Thuật toán được coi là hiệu quả hơn nếu thời gian thực hiện chương trình và lượng bộ nhớ mà máy tính cần dùng là ít hơn.
Cách tính giờ chạy thực thi chương trình cụ thể không áp dụng được khi muốn so sánh hiệu quả để lựa chọn thuật toán vì nó dẫn đến các vấn đề sau đây:
- Phải lập trình và chạy thử chương trình của tất cả các thuật toán cần so sánh.
- Thời gian đo được phụ thuộc vào nhiều yếu tố không liên quan tới thuật toán.
@201703726894@
2. Độ phức tạp thời gian của thuật toán
Thời gian chạy một chương trình với đầu vào có kích thước \(n\) sẽ là một hàm số \(T\left(n\right)\).
Độ phức tạp thời gian là kết quả ước lượng thời gian thực hiện các chương trình cài đặt thuật toán để xử lí một lượng dữ liệu đầu vào có độ lớn n.
Khó tính đếm chính xác con số này vì nhiều lí do:
- Bộ xử lí khó có thể xác định tương ứng số các phép toán bit với mỗi phép toán mà chúng ta vẫn biết như các phép toán số học (cộng, trừ, nhân, chia), các phép so sánh,...
- Ngay cả khi tính đếm số phép toán theo nghĩa thông thường với con người thì thế nào là một phép toán cũng không dễ thống nhất.
@203825606629@
3. Một số ví dụ cơ bản
| Độ phức tạp thời gian hằng số |
Độ phức tạp thời gian tuyến tính |
| Số phép toán cần thực hiện không phụ thuộc n. |
Nếu số phép toán cần thực hiện là hàm tuyến tính của n. |
| \(T\left(n\right)=3\) |
\(T\left(n\right)=n-1\) |
@203825689462@
4. Kí pháp và bậc tự do
Xét thuật toán tìm số lớn nhất trong dãy số:
- Tạm gán \(max=a_0\); đọc giá trị tiếp theo, so sánh với max và gán lại nếu cần.
- Khi phần tử đầu dãy a, có giá trị lớn nhất thì số lần phải gán lại giá trị \(max=a_0\) bằng 0. Số phép toán là ít nhất.
- Khi dãy số ban đầu là dãy tăng chặt, mọi số đều khác nhau, thì số lần phải gán \(a\) bằng n. Số phép toán là nhiều nhất.
Một cách tổng quát, có thể xét ba trường hợp: trường hợp thuận lợi nhất (số phép toán cần thực hiện ít nhất); trường hợp bất lợi nhất (số phép toán cần thực hiện nhiều nhất) và trường hợp ngẫu nhiên (số phép toán cần thực hiện ở mức trung bình).
| Kí hiệu O lớn |
Tên gọi |
| \(O\left(1\right)\) |
Hằng số |
| \(O\left(log_2n\right)\) |
Logarit |
| \(O\left(n\right)\) |
Tuyến tính |
| \(O\left(n^2\right)\) |
Bậc 2 |
| \(O\left(C^n\right)\) |
Hàm mũ |
| \(O\left(n!\right)\) |
Giai thừa |
Nếu \(f_1\left(n\right)=O\left(g_1\left(n\right)\right),f_2\left(n\right)=O\left(g_2\left(n\right)\right)\) thì:
- Công thức 1: \(O\left(f_1\left(n\right)+f_2\left(n\right)\right)=O(max\left(g_1\left(n\right),g_2\left(n\right)\right))\)
- Công thức 2: \(f_1\left(n\right)\times f_2\left(n\right)=O\left(g_1\left(n\right)\times g_2\left(n\right)\right)\)
❓Ví dụ. Hãy áp dụng quy tắc cộng cho một số hàm thời gian sau:
a) \(T\left(n\right)=10n+logn+3.\)
b) \(T\left(n\right)=5n^2+nlogn.\)
Giải
a) \(O\left(max\left(10n,logn,3\right)\right)=O\left(n\right)\)
b) \(O\left(max\left(5n^2,nlogn\right)\right)=O\left(n^2\right)\)
❓Ví dụ. Hãy áp dụng quy tắc nhân cho hàm \(T\left(n\right)=10n+nlogn+3.\)
Giải
\(T\left(n\right)=10n+nlogn+3=O\left(max\left(3n^2,nlogn\right)\right)=O\left(3n^2\right)=O\left(n^2\right)\)
@201704688452@@201704836136@
5. Các quy tắc ước lượng thời gian thực hiện
a) Quy tắc chung
Khi tính đếm số phép toán cần thực hiện, các quy tắc ước lượng cho phép bỏ bớt những phần có bậc lớn thấp hơn, chỉ giữ lại những phần có bậc lớn cao nhất và các hằng số nhân C đều coi là 1.
b) Lời gọi hàm
Một lời gọi hàm được chia làm hai trường hợp:
- Lời gọi các hàm toán học sơ cấp, các hàm thư viện,... với đầu vào là giá trị cụ thể không phụ thuộc n → \(T\left(n\right)=O\left(1\right)\).
- Trường hợp còn lại sẽ được ước lượng độ phức tạp như với một thuật toán.
c) Cấu trúc tuần tự và quy tắc lấy max
Cấu trúc tuần tự là một dãy gồm \(C\) phép toán; \(C\) là số xác định, không phụ thuộc \(n\).
- Nếu tất cả \(C\) phép toán là sơ cấp → \(T\left(n\right)=O\left(1\right)\).
- Thời gian thực hiện bằng ước lượng lớn nhất trong số các ước lượng của các phép toán có trong dãy.
d) Cấu trúc rẽ nhánh và quy tắc lấy max
Kiểm tra điều kiện là tính giá trị biểu thức logic gồm biểu thức số học và một phép so sánh → \(T\left(n\right)=O\left(1\right)\).
Độ phức tạp thời gian của cấu trúc rẽ nhánh là độ phức tạp thời gian lớn nhất trong các độ phức tạp thời gian của các nhánh.
e) Cấu trúc vòng lặp và quy tắc nhân
Thời gian thực hiện cấu trúc vòng lặp được tính bằng số lần lặp nhân với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp.
@203825986733@
Bạn có thể đánh giá bài học này ở đây