Pascal - Độ Phức Tạp Của Thuật Toán - Tài Liệu đại Học

Tài liệu đại học Toggle navigation

• Miễn phí (current)
• Danh mục
  • Khoa học kỹ thuật
  • Công nghệ thông tin
  • Kinh tế, Tài chính, Kế toán
  • Văn hóa, Xã hội
  • Ngoại ngữ
  • Văn học, Báo chí
  • Kiến trúc, xây dựng
  • Sư phạm
  • Khoa học Tự nhiên
  • Luật
  • Y Dược, Công nghệ thực phẩm
  • Nông Lâm Thủy sản
  • Ôn thi Đại học, THPT
  • Đại cương
  • Tài liệu khác
  • Luận văn tổng hợp
  • Nông Lâm
  • Nông nghiệp
  • Luận văn luận án
  • Văn mẫu
• Tài liệu khác

1. Home
2. Tài liệu khác
3. Pascal - Độ phức tạp của thuật toán

Trich dan Pascal - Độ phức tạp của thuật toán - pdf 17 Download miễn phí Pascal - Độ phức tạp của thuật toán Việc xây dựng một hàm T tổng quát như trên trong mọi trường hợp của thuật toán là một việc rất khó khăn, nhiều lúc không thể thực hiện được. Chính vì vậy mà người ta chỉ xây dựng hàm T cho một số trường hợp đáng chú ý nhất của thuật toán, thường là trường hợp tốt nhấtvàxấu nhất.Chúng ta trở lại ví dụ về thuật toán tìm hộp nặng nhất trong n hộp cho trước, nhưng lần này ta làm việc trên một thể hiện khác của vấn đề. Ðây là một thuật toán tương đối đơn giản nên chúng ta có thể tiến hành phân tích được độ phức tạp. Trước khi phân tích độ phức tạp, ta nhắc lại đôi điều về thuật toán này. http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-02-25-pascal_do_phuc_tap_cua_thuat_toan.Xtq65h46jm.swf /tai-lieu/de-tai-ung-dung-tren-liketly-59364/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Một chương trình máy tính thường được cài đặt dựa trên một thuật toán đúng để giải quyết bài toán hay vấn đề. Tuy nhiên, ngay cả khi thuật toán đúng, chương trình vẫn có thể không sử dụng được đối với một dữ liệu đầu vào nào đó vì thời gian để cho ra kết quả là quá lâu hay sử dụng quá nhiều bộ nhớ (vượt quá khả năng đáp ứng của máy tính). Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về thời gian và "không gian" cần thiết để thực hiện thuật toán. Không gian ở đây được hiểu là các yêu cầu về bộ nhớ, thiết bị lưu trữ, ... của máy tính để thuật toán có thể làm việc. Việc xem xét về không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu của thuật toán. Trong phần này, khi nói đến độ phức tạp của thuật toán, chúng ta chỉ đề cập đến những đánh giá về mặt thời gian mà thôi. Phân tích thuật toán là một công việc rất khó khăn, đòi hỏi phải có những hiểu biết sâu sắc về thuật toán và nhiều kiến thức toán học khác. Ðây là công việc mà không phải bất cứ người nào cũng làm được. Rất may mắn là các nhà toán học đã phân tích cho chúng ta độ phức tạp của hầu hết các thuật toán cơ sở (sắp xếp, tìm kiếm, các thuật toán số học, ...). Chính vì vậy, nhiệm vụ còn lại của chúng ta là hiểu được các khái niệm liên quan đến độ phức tạp của thuật toán. Ðánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt đối (chạy thuật toán mất bao nhiêu giây, bao nhiêu phút,...) để thực hiện thuật toán mà là xác định mối liên quan giữa dữ liệu đầu vào (input) của thuật toán và chi phí (số thao tác, số phép tính cộng,trừ, nhân, chia, rút căn,...) để thực hiện thuật toán. Sở dĩ người ta không quan tâm đến thời gian tuyệt đối của thuật toán vì yếu tố này phụ thuộc vào tốc độ của máy tính, mà các máy tính khác nhau thì có tốc độ rất khác nhau. Một cách tổng quát, chi phí thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào :T = f(input) Tuy vậy, khi phân tích thuật toán, người ta thường chỉ chú ý đến mối liên quan giữa độ lớn của dữ liệu đầu vào và chi phí. Trong các thuật toán, độ lớn của dữ liệu đầu vào thường được thể hiện bằng một con số nguyên n. Chẳng hạn : sắp xếp n con số nguyên, tìm con số lớn nhất trong n số, tính điểm trung bình của n học sinh, ... Lúc này, người ta thể hiện chi phí thực hiện thuật toán bằng một hàm số phụ thuộc vào n : T = f(n) Việc xây dựng một hàm T tổng quát như trên trong mọi trường hợp của thuật toán là một việc rất khó khăn, nhiều lúc không thể thực hiện được. Chính vì vậy mà người ta chỉ xây dựng hàm T cho một số trường hợp đáng chú ý nhất của thuật toán, thường là trường hợp tốt nhất và xấu nhất. Chúng ta trở lại ví dụ về thuật toán tìm hộp nặng nhất trong n hộp cho trước, nhưng lần này ta làm việc trên một thể hiện khác của vấn đề. Ðây là một thuật toán tương đối đơn giản nên chúng ta có thể tiến hành phân tích được độ phức tạp. Trước khi phân tích độ phức tạp, ta nhắc lại đôi điều về thuật toán này. Tìm số lớn nhất trong một dãy số Bài toán : Cho một dãy số a có n phần tử a1, a2, ...an. Hãy xây dựng thuật toán để tìm con số lớn nhất trong dãy a. Nhận xét 1. Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất. 2. Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ an+1 vào dãy mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược lại, nghĩa là an+1 £ amax thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử. Thuật toán 1. Ghi nhớ amax = a1. 2. i = 2. 3. Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5. 3.1. Nếu (ai > amax ) thì 3.1.1. Ghi nhớ amax = ai . 3.2. Tăng i lên 1. 4. Trở lại bước 3. 5. Phần tử lớn nhất dãy a chính là amax .Kết thúc. Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở bước 3.1 và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi con số lớn nhất nằm đầu dãy (amax= a1); trường hợp xấu nhất xảy ra khi con số lớn nhất nằm ở cuối dãy (amax=an) và dãy được sắp xếp theo thứ tự tăng dần. Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong mọi trường hợp của bài toán, phép "ghi nhớ" ở bước 3.1 luôn được thực hiện và số lần thực hiện là n-1 (ứng với việc xét từ phần tử a2 đến an). Ta gọi đây là chi phí cố định hay bất biến của thuật toán. Trường hợp tốt nhất : do amax = a1 suy ra, với mọi i ³ 2, ai< amax. Do đó, điều kiện ai>amax ở bước 3.1 luôn không thỏa nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là chi phí cố định của bài toán. T = f(n) = n-1 Trường hợp xấu nhất : Ta có : với mọi i>1, ai-1< ai (do định nghĩa dãy được sắp xếp tăng dần) nên điều kiện ai>amax ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí chung là n-1 phép so sánh, ta cần dùng thêm n-1 phép "ghi nhớ" ở bước 3.1.1. Như vậy, tổng chi phí của trường hợp này là T = f(n) = 2(n-1)=2n-2 Ðịnh nghĩa Cho hai hàm f và g có miền xác định trong tập số tự nhiên . Ta viết f(n) = O(g(n)) và nói f(n) có cấp cao nhất là g(n) khi tồn tại hằng số C và k sao cho | f(n) | £ C.g(n) với mọi n > k Tuy chi phí của thuật toán trong trường hợp tốt nhất và xấu nhất có thể nói lên nhiều điều nhưng vẫn chưa đưa ra được một hình dung tốt nhất về độ phức tạp của thuật toán. Ðể có thể hình dung chính xác về độ phức tạp của thuật toán, ta xét đến một yếu tố khác là độ tăng của chi phí khi độ lớn n của dữ liệu đầu vào tăng. Theo định nghĩa ở trên, ta nhận thấy chi phí thấp nhất và lớn nhất của thuật toán tìm số lớn nhất đều bị chặn bởi O(n) (tồn tại hằng số C=10, k=1 để 2n-2 1). Một cách tổng quát, nếu hàm chi phí của thuật toán (xét trong một trường hợp nào đó) bị chặn bởi O(f(n)) thì ta nói rằng thuật toán có độ phức tạp là O(f(n)) trong trường hợp đó. Như vậy, thuật toán tìm số lớn nhất có độ phức tạp trong trường hợp tốt nhất và xấu nhất đều là O(n). Người ta gọi các thuật toán có độ phức tạp O(n) là các thuật toán có độ phức tạp tuyến tính. Sau đây là một số "thước đo" độ phức tạp của thuật toán được sử dụng rộng rãi. Các độ phức tạp được sắp xếp theo thứ tự tăng dần. Nghĩa là một bài toán có độ phức tạp O(nk) sẽ phức tạp hơn bài toán có độ phức tạp O(n) hay O(logan). ... Yêu cầu Download Tài liệu, ebook tham khảo khác

• Pascal - Các phượng pháp biểu diễn thuật toán
• Ebook Tiếng Anh chuyên ngành tin học
• Các bước tạo bài giới thiệu xe máy tay ga Piagiio Vespa LX Việt Nam
• Pascal - Phạm vi tác dụng của các khai báo
• Một số giải pháp nhằm nâng cao khả năng thắng thầu của công ty công trình giao thông 208
• Đầu tư phát triển nông nghiệp Hà Tây
• Đầu tư nâng cao năng lực sản xuất kinh doanh ở công ty cổ phần tư vấn xây dựng sông Đà
• Tự học Excel 2007 - Công thức và hàm
• Cải tiến Windows Explorer với các tính năng từ FilerFrog
• Pascal - Thuật toán

Hệ thống tự động tổng hợp link tải tài liệu, ebook miễn phí cho các bạn sinh viên tham khảo.

Học thêm

• Nhờ tải tài liệu
• Từ điển Nhật Việt online
• Từ điển Hàn Việt online
• Văn mẫu tuyển chọn
• Tài liệu Cao học
• Tài liệu tham khảo
• Truyện Tiếng Anh

Music ♫

Copyright: Tài liệu đại học ©

Top