Ktl-icon-tai-lieu

Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán

Được đăng lên bởi tsunnytest
Số trang: 131 trang   |   Lượt xem: 603 lần   |   Lượt tải: 0 lần
Bài Giảng Môn Học Phân Tích Và Thiết
Kế Thuật Toán
Biên tập bởi:
Đại Học Phương Đông

Bài Giảng Môn Học Phân Tích Và Thiết
Kế Thuật Toán
Biên tập bởi:
Đại Học Phương Đông
Các tác giả:
Đại Học Phương Đông

Phiên bản trực tuyến:


MỤC LỤC
1. Độ phức tạp tính toán và tính hiệu quả của thuật toán
2. Mở đầu về thiết kế, đánh giá thuật toán và kiến thức bổ trợ
3. Phương pháp tham lam
4. Phương pháp “chia để trị”
5. Quy hoạch động
6. Thuật toán đồ thị cơ bản
Tham gia đóng góp

1/129

Độ phức tạp tính toán và tính hiệu quả của
thuật toán
Sự cần thiết phải phân tích thuật toán
Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề là
cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông thường
thì ta sẽ căn cứ vào các tiêu chuẩn sau:
1. Giải thuật đúng đắn.
2. Giải thuật đơn giản.
3. Giải thuật thực hiện nhanh.
Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải
thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu
được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì có
thể giải thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ
dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa chứng minh
được là nó đúng. Tính đúng đắn của giải thuật cần phải được chứng minh bằng toán học.
Tất nhiên điều này không đơn giản và do vậy chúng ta sẽ không đề cập đến ở đây.
Khi chúng ta viết một chương trình để sử dụng một vài lần thì y ê u cầu (2) là quan trọng
nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết quả,
thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng
chỉ sử dụng một vài lần mà thôi.
Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm thời
gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương trình mà
khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một cách kĩ càng.
Ta gọi nó là hiệu quả thời gian thực hiện của giải thuật.

Thời gian thực hiện của chương trình
Một phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật là lập trình
nó và đo lường thời gian thực hiện của hoạt động trên một máy tính xác định
2/129

đối với tập hợp được chọn lọc các dữ liệu vào.
Thời gian thực hiện không chỉ phụ thuộc vào giải thuật mà còn phụ thuộc vào tập
các chỉ thị của máy tính, chất lượng của máy tính và kĩ...
Bài Giảng Môn Học Phân Tích Và Thiết
Kế Thuật Toán
Biên tập bởi:
Đại Học Phương Đông
Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán - Người đăng: tsunnytest
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
131 Vietnamese
Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán 9 10 553