Báo cáo học liệu
Mua học liệu
Mua học liệu:
-
Số dư ví của bạn: 0 coin - 0 Xu
-
Nếu mua học liệu này bạn sẽ bị trừ: 0 coin\Xu
Để nhận Coin\Xu, bạn có thể:

Độ phức tạp thời gian thuật toán SVIP
Nội dung này do giáo viên tự biên soạn.
BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
chúng ta dễ thấy phép nhân hai số có n chữ số sẽ cần n2 phép nhân và 2n phép cộng, vậy tổng số các phép tính đơn của phép nhân này là n2 + 2n, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc m2.
1. Đánh giá thời gian thực hiện chương trình
* Nguyên tắc đơn vị tính thời gian thuật toán.
1. Các phép toán đơn giản như phép tính số học + - */ phép lấy thương nguyên và số dư, các phép so sánh sẽ tinh là 1 đơn vị thời gian.
2. Các phép toán lôgic cơ bản như AND, OR, NOT sẽ tính là 1 đơn vị thời gian.
3. Các lệnh đơn như lệnh gán, lệnh in, đọc dữ liệu.... tính là 1 đơn vị thời gian.
4. Vòng lặp for hoặc while sẽ được tính thời gian bằng tổng đơn vị thời gian thực hiện của mỗi bước lặp.
5. Lệnh if với nhiều trường hợp rẽ nhánh sẽ được tính thời gian bằng đơn vì thời gian lớn nhất của các lệnh nhánh.
→ Áp dụng các nguyên tắc tính khung thời gian trên chúng ta có thể tinh được gần chính xác thời gian thực hiện chương trình mà không cần cài đặt và chạy chương trình trên máy tính.
*Câu hỏi củng cố tr.113 SGK:
1. (a) T(n) =. (b) T(n) = + 1.
2. Phân tích độ phức tạp thời gian thuật toán
- Định nghĩa O-lớn (big-O):
Cho f(n) và g(n) là hai hàm có đối số tự nhiên. Ta viết f(n) = O(g(n)) và nói f(n) có bậc O-lớn của g(n) nếu tồn tại hằng số c > 0 và số tự nhiên n0 ≥ 1 sao cho với mọi n ≥ n0 ta có f(n) ≤ c.g(n). Nếu f(n) là O-lớn của g(n) thì có thể viết f(n) = O(g(n)).
hàm chuẩn như:
O(1) - hằng số
O(logn) - logarit
O(n) - tuyến tính
O(nlogn) - tuyến tính logarit
O(n2) - bình phương
O(nk) - đa thức
O(an) - lũy thừa
O(n!) - giai thừa.
* Luyện tập:
Câu 1: hàm thời gian T1(n) = n + 3.
Chọn c = 2, n0 = 3. Khi đó với n ≥ n0 ta có:
T1(n) = n + 3 ≤ n + n = c.n.
Do đó T1(n) = O(n). Chúng ta nói chương trình 1 có độ phức tạp thời gian O(n) - tuyến tính.
Câu 2: hàm thời gian T2(n) = n2 + 3.
Chọn c = 2, n0 = 2. Khi đó với n ≥ n0, ta có:
T2(n) = n2 + 3 < n2 + = 2n2 = c.n2.
Vậy suy ra T2(n) = O(n2). Ta nói chương trình 2 ở trên có độ phức tạp thời gian O(n2) - bình phương.
* Câu hỏi củng cố tr.114 SGK:
a) T(n) = O(n2).
b) T(n) = O(n3).
+ Hình bên mô tả các độ tăng của các hàm chuẩn.
.3. Một số quy tắc thực hành tính độ phức tạp thời gian thuật toán
- Quy tắc 1. Quy tắc cộng:
O(f(n) + g(n)) = O(max(f(n), g(n))
- Quy tắc 2. Quy tắc nhân:
Phép nhân với hàm số:
O(f(n).g(n)) = O(f(n).O(gn))).
Ví dụ: T(n) = 10n2 = O(n2).
T(n) = 3n2 + nlogn = O(max(3n2, nlogn)) (Quy tắc cộng) = O(3n2) = O(n2) (Quy tắc nhân với hằng số).
Khi nói đến bậc thời gian logarit thì hay chỉ viết O(logn) mà không viết cụ thể các hàm có cơ số, ví dụ log2n, log6n hay log10n vì tất cả các hàm logarit đó đều cùng bậc. Điều này suy từ công thức:
logan = logab.logbn
logab là hằng số nên theo quy tắc nhân ta có logan có cùng bậc với logbn..
Bạn có thể đăng câu hỏi về bài học này ở đây