zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Độ phức tạp của thuật toán - ThS. Hoàng Thị Thanh Hà

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

6
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc - Độ phức tạp của thuật toán, được biên soạn gồm các nội dung chính sau: Giới thiệu; Định nghĩa; Đánh giá thuật toán. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Độ phức tạp của thuật toán - ThS. Hoàng Thị Thanh Hà

Toán rời rạc (1b): ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Ths. Hoàng Th Thanh Hà Khoa Th ng kê –Tin h c Trư ng Đ i h c Kinh t Đ i h c Đà N ng 22 August 2012 1 Nội dung 1. Giới thiệu 2. Định nghĩa 3. Đánh giá thuật toán 22 August 2012 2 1
Giới thiệu Các thuật toán được đánh giá qua 2 chỉ tiêu: – Thời gian: là số thao tác mà thuật toán thực hiện tương ứng với kích thước nhập n – Không gian: là kích thước bộ nhớ mà thuật toán sử dụng Ví dụ 1: Xét thuật toán tìm số lớn nhất trong dãy n số a1, a2, ..., an. – Nếu coi mỗi lần so sánh hai số của thuật toán đòi hỏi một đơn vị thời gian (giây chẳng hạn) thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là n-1 giây. – Với dãy 64 số, thời gian thực hiện thuật toán nhiều lắm là 63 giây. 22 August 2012 3 Giới thiệu Ví dụ 2: Thuật toán về trò chơi “Tháp Hà Nội”: có ba cọc A, B, C và 64 cái đĩa, các đĩa có đường kính đôi một khác nhau. Nguyên tắc đặt đĩa vào cọc là: mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó. Ban đầu, cả 64 đĩa được đặt chồng lên nhau ở cột A; hai cột B, C trống. Vấn đề là phải chuyển cả 64 đĩa đó sang cột C, lấy cột B làm trung gian, mỗi lần chỉ được di chuyển một đĩa. – Gọi Sn là số lần chuyển đĩa để chơi xong trò chơi với n đĩa – Nếu n=1 thì rõ ràng là S1=1 – Nếu n>1 thì trước hết chuyển n-1 đĩa bên trên sang cọc B. Số lần chuyển n-1 đĩa là Sn-1. Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, ta chuyển n-1 đĩa từ cọc B sang cọc C (số lần chuyển là Sn-1). – => số lần chuyển n đĩa từ A sang C là: Sn=Sn-1+1+Sn+1=2Sn- 1+1=2(2Sn+2+1)+1=2.2Sn-2-+2+1=.....=2n-1S1+2n-2+...+2+1=2 −1. n 22 August 2012 4 2
Giới thiệu Thuật toán về trò chơi “Tháp Hà Nội” đòi hỏi 264−1 lần chuyển đĩa (xấp xỉ 18,4 tỉ tỉ lần). Nếu mỗi lần chuyển đĩa mất 1 giây thì thời gian thực hiện thuật toán xấp xỉ 585 tỉ năm! Thuật toán trong ví dụ 1 có độ phức tạp là n-1 và là một thuật toán hữu hiệu (hay thuật toán nhanh) Thuật toán trong ví dụ 2 có độ phức tạp là 2n−1 và đó là một thuật toán không hữu hiệu (hay thuật toán chậm) 22 August 2012 5 Định nghĩa Định nghĩa 1: Ta nói hàm f(n) có độ phức tạp thấp hơn hay bằng hàm g(n) nếu tồn tại hằng số C>0 và một số tự nhiên n0 sao cho: f(n) ≤ C. g(n) với ∀ n≥n0 ≥ – Ta viết f(n)=O(g(n)) và nói f(n) thoả mãn quan hệ big-O (hay O lớn) đối với g(n) – Theo định nghĩa này, hàm g(n) là một hàm đơn giản nhất có thể được, đại diện cho “sự biến thiên” của f(n) 22 August 2012 6 3
n( n + 3) 2 Định nghĩa Ví dụ 3: Hàm f(n)= n(n+3)/2 là hàm bậc hai và hàm bậc hai đơn giản nhất là n2. Ta có: – f(n)= n(n+3)/2 =O(n2) vì n(n+3)/2 ≤ n2 với mọi n≥3 ≥ (C=1, n0=3). 22 August 2012 7 n( n + 3) 2 Định nghĩa Định nghĩa 2: Nếu một thuật toán có độ phức tạp là f(n) với f(n)=O(g(n)) thì ta cũng nói thuật toán f(n) có độ phức tạp O(g(n)) – g(n) thường là hàm đơn thức Ví dụ: f(n)=n2 +7n, g(n) =n2 – Ta có f(n)= O(g(n)), ta nói f(n) có độ phức tạp là O(n2) 22 August 2012 8 4
n( n + 3) 2 Đánh giá thuật toán Quy ước: – Lệnh gán, lệnh ghi có độ phức tạp là O(1) – Lệnh vào ra có độ phức tạp là O(1) – Lệnh If … else có độ phức tạp là max của 2 nhánh – Lệnh lặp là số lần lặp nhân với số thao tác ở mỗi bước – Quy tắc cộng: O(f+g) = max{O(f) + O(g)} – Quy tắc nhân O(f.g) = O(f). O(g) 22 August 2012 9 n( n + 3) 2 Đánh giá thuật toán Ví dụ: thuật toán tìm kiếm tuyến tính giá trị x trên mảng A gồm n phần tử. – Trường hợp tốt nhất: x nằm đầu danh sách, thì độ phức tạp là bằng O(1) – Trường hợp xấu nhất: x nằm cuối danh sách hoặc không tồn tại trong A, thì độ phức tạp là bằng O(n) 22 August 2012 10 5
n( n + 3) 2 Đánh giá thuật toán Ví dụ: thuật toán tìm kiếm nhị phân giá trị x trên mảng A gồm n phần tử đã được sắp xếp. – Trường hợp tốt nhất: x nằm giữa danh sách, thì độ phức tạp là bằng O(1) – Trường hợp xấu nhất: giả sử n= 2k, thì cứ mỗi bước thực hiện, độ dài của dãy còn lại bằng 2k-1, như vậy thực hiện k bước thì thuật toán dừng. Như vậy độ phức tạp là bằng O(k) = O(log2n) 22 August 2012 11 n( n + 3) 2 Đánh giá thuật toán đệ quy Thuật toán đệ quy: – Thuật toán sử dụng lại lời gọi chính nó trong quá trình tính toán và xử lý (thường là một hàm). Các đặc điểm của một hàm đệ quy: – Phần cơ sở: những giá trị đặc biệt (hay gọi là giá trị neo) mà hàm trả về giá trị (hoặc thực hiện công việc) chứ không gọi lại hàm – Phần đệ quy: Thực hiện công việc tại giá trị hiện thời và gọi lại hàm với tham số thay đổi (suy giảm) theo chiều hướng trở về giá trị neo 22 August 2012 12 6
n( n + 3) 2 Đánh giá thuật toán đệ quy Ví dụ thuật toán đệ quy: hàm tính giai thừa: GiaiThua(0)=1 (giá trị neo là 0) GiaiThua(n)=n*GiaiThua(n-1) (phần đệ quy) Xây dựng hàm đệ quy: Int GiaiThua(int n) { If (n=0) return 1 Else return n*GiaiThua(n-1) } Nếu n=0 thì độ phức tạp O(1) Nếu n>0 thì độ phức tạp là O(n) 22 August 2012 13 n( n + 3) 2 Đánh giá thuật toán đệ quy Ví dụ thuật toán đệ quy: hàm tính dãy số Fibonaci: F(0)=1, F(1)=1 (giá trị neo là 1) F(n)= F(n-1) + F(n-2) (phần đệ quy) Xây dựng hàm đệ quy: Int F(int n) { If (n
n( n + 3) 2 Đánh giá thuật toán đệ quy Ví dụ thuật toán đệ quy: hàm tính dãy số Fibonaci: F(0)=1, F(1)=1 (giá trị neo là 1) F(n)= F(n-1) + F(n-2) (phần đệ quy) Xây dựng hàm khử đệ quy: Int F(int n) { Int F0=1, F1=1, I, fn=1; For (i=2; i
n( n + 3) 2 Các thuật ngữ dùng cho độ phức tạp của thuật toán Độ phức tạp Thuật ngữ O(1) Độ phức tạp hằng số O(logn) Độ phức tạp logarit O(n) Độ phức tạp tuyến tính O(nlogn) Độ phức tạp nlogn O(nb) Độ phức tạp đa thức O(bn), b>1 Độ phức tạp hàm mũ O(n!) Độ phức tạp giai thừa 22 August 2012 17 9

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.