Tài liệu Tổ chức dữ liệu cho lớp thuật toán chia để trị và ứng dụng

1 ĐẠI HỌC THÁI NGUYÊN .. TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG Đỗ Tuấn Anh TỔ CHỨC DỮ LIỆU CHO LỚP THUẬT TOÁN CHIA ĐỂ TRỊ VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của bản thân, được xuất phát từ yêu cầu phát sinh trong công việc để hình thành hướng nghiên cứu. Các số liệu có nguồn gốc rõ ràng tuân thủ đúng nguyên tắc và kết quả trình bày trong luận văn được thu thập được trong quá trình nghiên cứu là trung thực chưa từng được ai công bố trước đây. Thái Nguyên, ngày 19 tháng 5 năm 2014 Học viên thực hiên Đỗ Tuấn Anh Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 3 LỜI CẢM ƠN Đầu tiên, em xin gửi lời cảm ơn sâu sắc nhất đến cán bộ hướng dẫn khoa học, thầy giáo, PGS.TSKH Nguyễn Xuân Huy, người đã truyền cho em nguồn cảm hứng nghiên cứu khoa học, người đã định hướng cho em đến với lĩnh vực nghiên cứu này. Em xin bày tỏ lời cảm ơn tới các thầy giáo, cô giáo đã giảng dạy em trong suốt hai năm học qua. Em cũng muốn gửi lời cảm ơn tới những thành viên lớp đã có những góp ý chuyên môn cũng như sự động viên về tinh thần rất đáng trân trọng. Cuối cùng, em xin gửi lời cảm ơn sâu sắc tới tất cả người thân trong gia đình và những bạn bè em với những động viên dành cho em trong công việc và trong cuộc sống. Học viên thực hiện luận văn Đỗ Tuấn Anh Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 4 MỤC LỤC Trang Lời cam đoan Lời cảm ơn Mục lục ............................................................................................................................ iii Danh mục các bảng ...........................................................................................................v Danh mục các hình vẽ .......................................................................................................v MỞ ĐẦU...........................................................................................................................1 CHƢƠNG 1. CÁC CHIẾN LƢỢC THIẾT KẾ THUẬT TOÁN................................2 1.1 Các bước cơ bản khi giải bài toán trên máy tính ........................................................2 1.2 Phân tích thời gian thực hiện thuật toán ......................................................................6 1.2.1 Độ phức tạp thuật toán .............................................................................................6 1.2.2 Xác định độ phức tạp của thuật toán ........................................................................9 1.2.3 Ký hiệu Big-O và biểu diễn thời gian chạy của thuật toán ....................................10 1.2.4 Độ phức tạp thuật toán với tình trạng dữ liệu vào..................................................13 1.2.5 Chi phí thực hiện thuật toán ...................................................................................13 CHƢƠNG 2. TỔ CHỨC DỮ LIỆU CHO LỚP THUẬT TOÁN CHIA ĐỂ TRỊ ...14 2.1 Chiến lược chia để trị ...............................................................................................14 2.2 Tổ chức dữ liệu cho lớp thuật toán chia để trị ..........................................................15 2.3 Định lý tổng quát tính độ phức tạp các thuật toán chia để trị...................................16 2.4 Một số lớp bài toán điển hình ...................................................................................17 2.4.1 Lớp bài toán tìm kiếm ............................................................................................18 2.4.1.1 Thuật toán tìm kiếm nhị phân .............................................................................18 2.4.1.2 Bài toán tìm Max và min .....................................................................................20 2.4.2 Lớp bài toán sắp xếp...............................................................................................22 2.4.2.1 Thuật toán sắp xếp trộn (Merge Sort) .................................................................22 2.4.2.2 Thuật toán sắp xếp nhanh (Quick Sort) ...............................................................24 2.4.3 Lớp bài toán tối ưu .................................................................................................27 2.4.3.1 Bài toán dãy con dài nhất ....................................................................................27 2.3.3.2 Bài toán tháp Hà Nội ...........................................................................................29 2.3.3.5 Bài toán xếp lịch thi đấu ......................................................................................30 CHƢƠNG 3. ỨNG DỤNG THUẬT TOÁN CHIA ĐỂ TRỊ GIẢI BÀI TOÁN NHÂN HAI SỐ NGUYÊN LỚN ..................................................................................32 3.1 Mô tả bài toán ............................................................................................................32 3.2 Thuật toán nhân tự nhiên ...........................................................................................32 3.3 Thuật toán nhân cơ bản .............................................................................................33 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 5 3.4 Thuật toán nhân Karatsuba-Ofman ...........................................................................35 3.5 Thuật toán nhân dựa trên biến đổi Fourier nhanh .....................................................37 3.6 Thuật toán nhân chia để trị ........................................................................................40 3.6.1 Ý tưởng chung ........................................................................................................40 3.6.2 Phân tích thuật toán ................................................................................................41 3.6.3 Mô hình thuật toán chia để trị cho bài toán nhân hai số nguyên lớn .....................44 3.6.4 So sánh độ phức tạp giữa các thuật toán ................................................................46 3.7 Tổ chức dữ liệu cho thuật toán chia để trị .................................................................46 3.7.1 Biểu diễn dưới dạng bit ..........................................................................................46 3.7.2 Biểu diễn dùng mảng và xâu ..................................................................................47 3.8 Thực nghiệm và đánh giá ..........................................................................................51 3.8.1 Cài đặt trên C ..........................................................................................................51 3.8.2 Cài đặt trên C# ........................................................................................................59 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................................64 TÀI LIỆU THAM KHẢO ............................................................................................65 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 6 DANH MỤC CÁC BẢNG Bảng 1.1 Các lớp độ phức tạp tính toán .............................................................................. 11 Bảng 1.2 Thời gian chạy của các lớp thuật toán.................................................................. 12 Bảng 2.1 Độ phức tạp của thuật toán tìm kiếm nhị phân .................................................... 20 Bảng 2.2 Độ phức tạp của thuật toán sắp xếp nhanh........................................................... 26 Bảng 3.1 So sánh độ phức tạp tính toán của các thuật toán nhân ....................................... 46 DANH MỤC CÁC HÌNH Hình 2.1 Thuật toán chia để trị ............................................................................................ 14 Hình 2.2 Tổ chức dữ liệu cho lớp bài toán chia để trị ........................................................ 15 Hình 2.3 Ví dụ thuật toán sắp xếp trộn ................................................................................ 23 Hình 3.1 Thuật toán nhân Brute-force ................................................................................. 33 Hình 3.2 Thuật toán nhân chuẩn.......................................................................................... 34 Hình 3.3 Thuật toán nhân SRMA ........................................................................................ 35 Hình 3.4 Thuật toán nhân Karatsuba-Ofman ...................................................................... 37 Hình 3.5 Thuật toán nhân FFT ............................................................................................ 39 Hình 3.6 Thuật toán nhân chia để trị ................................................................................... 45 Hình 3.7 Phép nhân chia để trị tổ chức dưới dạng bit ......................................................... 46 Hình 3.8 Thuật toán nhân chia để trị biểu diễn bit .............................................................. 47 Hình 3.9 Ví dụ về phép chia Ấn Độ Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 7 MỞ ĐẦU .Ngày nay phương pháp này vẫn còn được áp dụng trong nhiều lĩnh vực của đời sống. Đặc biệt, phương pháp này rất hiệu quả khi thiết kế thuật toán giải các bài toán lớn, phức tạp. Với bài toán đầu vào rất lớn ta chia thành những phần nhỏ hơn và tìm lời giải cho các bài toán nhỏ riêng biệt này, rồi sau đó tổng hợp các nghiệm riêng rẽ thành nghiệm bài toán toàn cục. Trong luận văn này, tôi sẽ tập trung phân tích việc tổ chức dữ liệu cho lớp thuật toán chia để trị và cách đánh giá độ phức tạp đối với các thuật toán chia để trị.Với mục tiêu chính là áp dụng thiết kế thuật toán chia để trị để giải quyết bài toán nhân hai số nguyên lớn, luận văn được trình bày trong 3 chương với bố cục như sau: Chƣơng 1: Các chiến lƣợc thiết kế thuật toán. Giới thiệu tổng quan về các bước giải bài toán trên máy tính và phân tích đánh giá thời gian thực hiện thuật toán cùng các chiến lược thiết kế thuật toán cơ bản. Chƣơng 2: Tổ chức dữ liệu cho lớp thuật toán chia để trị.Trình bày ý tưởng, cơ sở khoa học của thuật toán chia để trị và cách thức tổ chức dữ liệu cho thuật toán chia để trị với các bài toán kinh điển. Chƣơng 3: Ứng dụng thuật toán chia để trị giải bài toán nhân hai số nguyên lớn. Tập trung phân tích các cách tiếp cận giải bài toán nhân hai số nguyên lớn. Từ đó đề xuất thuật toán dựa trên tư tưởng chia để trị để giải quyết và thực nghiệm so sánh với các cách tiếp cận trước đó. Cuối cùng là kết luận và hƣớng phát triển:Tóm tắtnhững kết quả đạt được, những hạn chế và nêu lên các hướng phát triển trong tương lai. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 8 CHƢƠNG 1. CÁC CHIẾN LƢỢC THIẾT KẾ THUẬT TOÁN 1.1 Các bƣớc cơ bản khi giải bài toán trên máy tính Một thuật toán một thủ tục tính toán được định nghĩa chính xác, mà lấy một giá trị hoặc một tập các giá trị, được gọi là đầu vào hay dữ liệu vào và tạo ra một giá trị, hoặc một tập các giá trị, và gọi là đầu ra. Miêu tả một vấn đề thường được xác định nói chungqua quan hệ đầu vào/đầu ra. Một thuật toán là một dãy bước xác định để chuyển đổi dữ liệu đầu vào thành dữ liệu đầu ra. Chúng ta có thể xem một thuật toán như một công cụ để giải quyết một vấn đề tính toán. Việc trình bày rõ ràng một vấn đề nói chung hình thành mối quan hệ mong muốn đầu vào/đầu ra. Một thuật toán mô tả chính xác một thủ tục tính toán để đạt được mối liên hệ giữa dữ liệu đầu vào và dữ liệu đầu ra. 1.1.1 Xác định bài toán Việc xác định bài toán tức là phải xác định xem ta phải giải quyết vấn đề gì? với giả thiết nào đã cho và lời giải cần phải đạt những yêu cầu nào. Khác với bài toán thuần tuý toán học chỉ cần xác định rõ giả thiết và kết luận chứ không cần xác định yêu cầu về lời giải, đôi khi những bài toán tin học ứng dụng trong thực tế chỉ cần tìm lời giải tốt tới mức nào đó, thậm chí là tồi ở mức chấp nhận được. Bởi lời giải tốt nhất đòi hỏi quá nhiều thời gian và chi phí. Input → Process → Output (Dữ liệu vào →Xử lý →Kết quả ra) Ví dụ: Khi cài đặt các hàm số phức tạp trên máy tính. Nếu tính bằng cách khai triển chuỗi vô hạn thì độ chính xác cao hơn nhưng thời gian chậm hơn hàng tỉ lần so với phương pháp xấp xỉ. Trên thực tế việc tính toán luôn luôn cho phép chấp nhận một sai số nào đó nên các hàm số trong máy tính đều được tính bằng phương pháp xấp xỉ của giải tích số. Xác định đúng yêu cầu bài toán là rất quan trọng bởi nó ảnh hưởng tới cách thức giải quyết và chất lượng của lời giải. Một bài toán thực tế thường cho bởi những thông tin khá mơ hồ và hình thức, ta phải phát biểu lại một cách chính xác và chặt chẽ để hiểu đúng bài toán. Trên thực tế, ta nên xét một vài trường hợp cụ thể để thông qua đó hiểu được bài toán rõ hơn và thấy được các thao tác cần phải tiến hành. Đối với những bài toán đơn giản, đôi khi chỉ cần qua ví dụ là ta đã có thể đưa về một bài toán quen thuộc để giải. 1.1.2 Tìm cấu trúc dữ liệu biểu diễn bài toán Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 9 Khi giải một bài toán, ta cần phải định nghĩa tập hợp dữ liệu để biểu diễn tình trạng cụ thể. Việc lựa chọn này tuỳ thuộc vào vấn đề cần giải quyết và những thao tác sẽ tiến hành trên dữ liệu vào. Có những thuật toán chỉ thích ứng với một cách tổ chức dữ liệu nhất định, đối với những cách tổ chức dữ liệu khác thì sẽ kém hiệu quả hoặc không thể thực hiện được. Chính vì vậy nên bước xây dựng cấu trúc dữ liệu không thể tách rời bước tìm kiếm thuật toán giải quyết vấn đề. Các tiêu chuẩn khi lựa chọn cấu trúc dữ liệu: - Phải biểu diễn được đầy đủ các thông tin nhập và xuất của bài toán - Phù hợp với các thao tác của thuật toán mà ta lựa chọn để giải quyết bài toán. - Phải cài đặt được trên máy tính với ngôn ngữlập trình đang sửdụng. Đối với một sốbài toán, trước khi tổchức dữliệu ta phải viết một đoạn chương trình nhỏ để khảosátxem dữliệu cần lưu trữlớn tới mức độnào. 1.1.3 Xây dựng thuật toán Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy thao tác trên cấu trúc dữ liệu sao cho: Với một bộ dữ liệu vào, sau một số hữu hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định.Các đặc trưng của thuật toán: 1. Tính đơn định: Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lộn xộn, tuỳ tiện, đa nghĩa. Thực hiện đúng các bước của thuật toán thì với một dữ liệu vào, chỉ cho duy nhất một kết quả ra. 2. Tính dừng: Thuật toán không được rơi vào quá trình vô hạn, phải dừng lại và cho kết quả sau một số hữu hạn bước. 3. Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng quá trình đã định, ta phải được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả đó được kiểm chứng bằng yêu cầu bài toán. 4. Tính phổ dụng: Thuật toán phải dễ sửa đổi để thích ứng được với bất kỳ bài toán nào trong một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau. 5. Tính khả thi:Đối với một bài toán, có thể có nhiều thuật toán nhưng chúng phải cho cùng một output đối với một input. Tuy nhiên chúng có thể khác nhau về hiệu quả. Hiệu quả thời gian là tốc độ xử lý là nhanh hay chậm. Ta có thể đánh giá căn cứ vào số bước thực hiện. Hiệu quả không gian là không gian lưu trữ theo số các đối tượng dùng để ghi nhớ các kết quả (kể cả kết quả trung gian). Trong Tin học có cả một ngành chuyên đánh giá độ phức tạp của giải thuật, chủ yếu là đánh giá về hiệu quả thời gian. Thực tế sử dụng cho thấy thách thức về không gian lưu trữ có thể giải quyết dễ hơn thách thức về thời gian thực hiện. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 10 1.1.4 Lập trình Sau khi đã có thuật toán, ta phải tiến hành lập trình thể hiện thuật toán đó. Muốn lập trình đạt hiệu quả cao, cần phải có kỹ thuật lập trình tốt. Kỹ thuật lập trình tốt thể hiện ở kỹ năng viết chương trình, khả năng gỡ rối và thao tác nhanh. Lập trình tốt không phải chỉ cần nắm vững ngôn ngữ lập trình là đủ mà phải biết cách viết chương trình uyển chuyển, phát triển từng bước để chuyển các ý tưởng ra thành chương trình hoàn chỉnh. Kinh nghiệm cho thấy một thuật toán hay nhưng do cài đặt vụng về nên khi chạy lại cho kết quả sai hoặc tốc độ chậm. Thông thường, chúng ta không nên cụ thể hoá ngay toàn bộ chương trình mà nên tiến hành theo phương pháp tinh chế từng bước (Stepwiserefinement): - Ban đầu, chương trình được thể hiện bằng ngôn ngữ tự nhiên, thể hiện thuật toán với các bước tổng thể, mỗi bước nêu lên một công việc phải thực hiện. - Một công việc đơn giản hoặc là một đoạn chương trình đã được học thuộc thì ta tiến hành viết mã lệnh ngay bằng ngôn ngữ lập trình. - Một công việc phức tạp thì ta lại chia ra thành những công việc nhỏ hơn để lại tiếp tục với những công việc nhỏ hơn đó. Trong quá trình tinh chế từng bước, ta phải đưa ra những biểu diễn dữ liệu. Như vậy cùng với sự tinh chế các công việc, dữ liệu cũng được tinh chế dần, có cấu trúc hơn, thể hiện rõ hơn mối liên hệ giữa các dữ liệu.Phương pháp tinh chếtừng bước là một thểhiện của tưduy giải quyết vấn đềtừtrên xuống, giúpcho người lập trình có được một định hướng thểhiện trong phong cách viết chương trình. Tránhviệc mò mẫm, xoá đi viết lại nhiều lần, biến chương trình thành tờgiấy nháp. 1.1.5 Chạy và kiểm thử 1.1.5.1 Chạy thử và tìm lỗi Chương trình là do con người viết ra, mà đã là con người thì ai cũng có thể nhầm lẫn. Một chương trình viết xong chưa chắc đã chạy được ngay trên máy tính để cho ra kết quả mong muốn. Kỹ năng tìm lỗi, sửa lỗi, điều chỉnh lại chương trình cũng là một kỹ năng quan trọng của người lập trình. Kỹ năng này chỉ có được bằng kinh nghiệm tìm và sửa chữa lỗi của chính mình.Có ba loại lỗi: - Lỗi cú pháp: Lỗi này hay gặp nhất nhưng lại dễ sửa nhất, chỉ cần nắm vững ngôn ngữ lập trình là đủ. Một người được coi là không biết lập trình nếu không biết sửa lỗi cú pháp. - Lỗi cài đặt: Việc cài đặt thể hiện không đúng thuật toán đã định, đối với lỗi này thì phải xem lại tổng thể chương trình, kết hợp với các chức năng gỡ rối để sửa lại cho đúng. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 11 - Lỗi thuật toán: Lỗi này ít gặp nhất nhưng nguy hiểm nhất, nếu nhẹ thì phải điều chỉnh lại thuật toán, nếu nặng thì có khi phải loại bỏ hoàn toàn thuật toán sai và làm lại từ đầu. 1.1.5.2 Xây dựng các bộ dữ liệu kiểm tra Có nhiều chương trình rất khó kiểm tra tính đúng đắn. Nhất là khi ta không biết kết quả đúng là thế nào? Vì vậy nếu như chương trình vẫn chạy ra kết quả thì việc tìm lỗi rất khó khăn. Khi đó ta nên làm các bộ dữ liệu test để thử chương trình của mình. Kinh nghiệm khi xây dựng các bộ dữ liệu test là: - Bắt đầu với một bộ test nhỏ, đơn giản, làm bằng tay cũng có được đáp số để so sánh với kết quả chương trình chạy ra. - Tiếp theo vẫn là các bộ test nhỏ, nhưng chứa các giá trị đặc biệt hoặc tầm thường. Kinh nghiệm cho thấy đây là những test dễ sai nhất. - Các bộ test phải đa dạng, tránh sự lặp đi lặp lại các bộ test tương tự. - Có một vài test lớn chỉ để kiểm tra tính chịu đựng của chương trình mà thôi. Kết quả có đúng hay không thì trong đa số trường hợp, ta không thể kiểm chứng được với test này. Lưu ý rằng chương trình chạy qua được hết các test không có nghĩa là chương trình đó đã đúng. Bởi có thể ta chưa xây dựng được bộ test làm cho chương trình chạy sai. Vì vậy nếu có thể, ta nên tìm cách chứng minh tính đúng đắn của thuật toán và chương trình, điều này thường rất khó. 1.1.6 Tối ƣu chƣơng trình Một chương trình đã chạy đúng không có nghĩa là việc lập trình đã xong, ta phải tiếp tục cải tiến cấu trúc dữ liệu sửa đổi lại một vài chi tiết để có thể chạy nhanh hơn, hiệu quả hơn. Thông thường, trước khi kiểm thử thì ta nên đặt mục tiêu viết chương trình sao cho đơn giản, miễn sao chạy ra kết quả đúng là được, sau đó khi tối ưu chương trình, ta xem lại những chỗ nào viết chưa tốt thì tối ưu lại mã lệnh để chương trình ngắn hơn, chạy nhanh hơn. Không nên viết tới đâu tối ưu mã đến đó, bởi chương trình có mã lệnh tối ưu thường phức tạp và khó kiểm soát.Ta nên tối ưu chương trình theo các tiêu chuẩn sau: 1. Tính tin cậy: Chương trình phải chạy đúng như dự định, mô tả đúng một giải thuật đúng. Thông thường khi viết chương trình, ta luôn có thói quen kiểm tra tính đúng đắn của các bước mỗi khi có thể. 2. Tính uyển chuyển: Chương trình phải dễ sửa đổi. Bởi ít có chương trình nào viết ra đã hoàn hảo ngay được mà vẫn cần phải sửa đổi lại. Chương trình viết dễ sửa đổi sẽ làm giảm bớt công sức của lập trình viên khi phát triển chương trình. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 12 3. Tính trong sáng: Chương trình viết ra phải dễ đọc dễ hiểu, để sau một thời gian dài, khi đọc lại còn hiểu mình làm cái gì? Để nếu có điều kiện thì còn có thể sửa sai (nếu phát hiện lỗi mới), cải tiến hay biến đổi để được chương trình giải quyết bài toán khác. Tính trong sáng của chương trình phụ thuộc rất nhiều vào công cụ lập trình và phong cách lập trình. 4. Tính hữu hiệu: Chương trình phải chạy nhanh và ít tốn bộ nhớ, tức là tiết kiệm được cả về không gian và thời gian. Để có một chương trình hữu hiệu, cần phải có giải thuật tốt và những tiểu xảo khi lập trình. Tuy nhiên, việc áp dụng quá nhiều tiểu xảo có thể khiến chương trình trở nên rối rắm, khó hiểu khi sửa đổi. Tiêu chuẩn hữu hiệu nên dừng lại ở mức chấp nhận được, không quan trọng bằng ba tiêu chuẩn trên. Bởi phần cứng phát triển rất nhanh, yêu cầu hữu hiệu không cần phải đặt ra quá nặng. Từ những phân tích ở trên, chúng ta nhận thấy rằng việc làm ra một chương trình đòi hỏi rất nhiều công đoạn và tiêu tốn khá nhiều công sức. Chỉ một công đoạn không hợp lý sẽ làm tăng chi phí viết chương trình. Nghĩ ra cách giải quyết vấn đề đã khó, biến ý tưởng đó thành hiện thực cũng không dễ chút nào. 1.2 Phân tích thời gian thực hiện thuật toán 1.2.1 Độ phức tạp thuật toán Với một vấn đề đặt ra có thể có nhiều thuật toán giải, chẳng hạn người ta đã tìm ra rất nhiều thuật toán sắp xếp một mảng dữ liệu. Trong các trường hợp như thế, khi cần sử dụng thuật toán người ta thường chọn thuật toán có thời gian thực hiện ít hơn các thuật toán khác. Mặt khác, khi bạn đưa ra một thuật toán để giải quyết một vấn đề thì một câu hỏi đặt ra là thuật toán đó có ý nghĩa thực tế không? Nếu thuật toán đó có thời gian thực hiện quá lớn chẳng hạn hàng năm, hàng thế kỉ thì đương nhiên không thể áp dụng thuật toán này trong thực tế. Như vậy chúng ta cần đánh giá thời gian thực hiện thuật toán. Phân tích thuật toán, đánh giá thời gian chạy của thuật toán là một lĩnh vực nghiên cứu quan trong của khoa học máy tính. Trong chương này, chúng ta sẽ nghiên cứu phương pháp đánh giá thời gian chạy của thuật toán bằng cách sử dụng ký hiệu ô lớn, và chỉ ra cách đánh giá thời gian chạy thuật toán bằng ký hiệu ô lớn. Trước khi đi tới mục tiêu trên, chúng ta sẽ thảo luận ngắn gọn một số vấn đề liên quan đến thuật toán và tính hiệu quả của thuật toán. 1.2.1.1 Tính hiệu quả của thuật toán Như đã phân tích ở trên, chúng ta thường xem xét thuật toán, lựa chọn thuật toán để áp dụng dựa vào các tiêu chí sau: 1. Thuật toán đơn giản, dễ hiểu. 2. Thuật toán dễ cài đặt (dễ viết chương trình) 3. Thuật toán cần ít bộ nhớ Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 13 4. Thuật toán chạy nhanh Khi cài đặt thuật toán chỉ để sử dụng một số ít lần, người ta thường lựa chọn thuật toán theo tiêu chí 1 và 2. Tuy nhiên, có những thuật toán được sử dụng rất nhiều lần, trong nhiều chương trình, chẳng hạn các thuật toán sắp xếp, các thuật toán tìm kiếm, các thuật toán đồ thị…Trong các trường hợp như thế người ta lựa chọn thuật toán để sử dụng theo tiêu chí 3 và 4. Hai tiêu chí này được nói tới như là tính hiệu quả của thuật toán. Tính hiệu quả của thuật toán gồm hai yếu tố: dung lượng bộ nhớ mà thuật toán đòi hỏi và thời gian thực hiện thuật toán. Dung lượng bộ nhớ gồm bộ nhớ dùng để lưu dữ liệu vào, dữ liệu ra, và các kết quả trung gian khi thực hiện thuật toán; dung lượng bộ nhớ mà thuật toán đòi hỏi còn được gọi là độ phức tạp không gian của thuật toán. Thời gian thực hiện thuật toán được nói tới như là thời gian chạy (Running time) hoặc độ phức tạp thời gian của thuật toán. Sau này chúng ta chỉ quan tâm tới đánh giá thời gian chạy của thuật toán. Đánh giá thời gian chạy của thuật toán bằng cách nào? Với cách tiếp cận thực nghiệm chúng ta có thể cài đặt thuật toán và cho chạy chương trình trên một máy tính nào đó với một số dữ liệu vào. Thời gian chạy mà ta thu được sẽ phụ thuộc vào nhiều nhân tố: - Kỹ năng của người lập trình - Chương trình dịch - Tốc độ thực hiện các phép toán của máy tính - Dữ liệu vào Vì vậy, trong cách tiếp cận thực nghiệm, ta không thể nói thời gian chạy của thuật toán là bao nhiêu đơn vị thời gian. Chẳng hạn câu nói “thời gian chạy của thuật toán là 30 giây” là không thể chấp nhận được. Nếu có hai thuật toán A và B giải quyết cùng một vấn đề, ta cũng không thể dùng phương pháp thực nghiệm để kết luận thuật toán nào chạy nhanh hơn, bởi vì ta mới chỉ chạy chương trình với một số dữ liệu vào.Một cách tiếp cận khác để đánh giá thời gian chạy của thuật toán là phương pháp phân tích sử dụng các công cụ toán học. Chúng ta mong muốn có kết luận về thời gian chạy của một thuật toán mà nó không phụ thuộc vào sự cài đặt của thuật toán, không phụ thuộc vào máy tính mà trên đó thuật toán được thực hiện. Để phân tích thuật toán chúng ta cần sử dụng khái niệm cỡ (size) của dữ liệu vào. Cỡ của dữ liệu vào được xác định phụ thuộc vào từng thuật toán. Ví dụ, trong thuật toán tính định thức của ma trận vuông cấp n, ta có thể chọn cỡ của dữ liệu vào là cấp n của ma trận; còn đối với thuật toán sắp xếp mảng cỡ n thì cỡ của dữ liệu vào chính là cỡ n của mảng. Đương nhiên là có vô số dữ liệu vào cùng một cỡ. Nói chung trong phần lớn các thuật toán, cỡ của dữ liệu vào là một số nguyên dương n. Thời gian chạy của thuật toán phụ thuộc vào cỡ của dữ liệu vào; chẳng hạn tính định thức của ma trận cấp 20 đòi hỏi thời gian chạy nhiều hơn tính định thức của ma trận cấp 10. Nói chung, cỡ của dữ liệu càng lớn Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 14 thì thời gian thực hiện thuật toán càng lớn. Nhưng thời gian thực hiện thuật toán không chỉ phụ thuộc vào cỡ của dữ liệu vào mà còn phụ thuộc vào chính dữ liệu vào. Trong số các dữ liệu vào cùng một cỡ, thời gian chạy của thuật toán cũng thay đổi. Chẳng hạn, xét bài toán tìm xem đối tượng a có mặt trong danh sách (a1,…,ai,…,an) hay không. Thuật toán được sử dụng là thuật toán tìm kiếm tuần tự: Xem xét lần lượt từng phần tử của danh sách cho tới khi phát hiện ra đối tượng cần tìm thì dừng lại, hoặc đi hết danh sách mà không gặp phần tử nào bằng a. Ở đây cỡ của dữ liệu vào là n, nếu một danh sách với a là phần tử đầu tiên, ta chỉ cần một lần so sánh và đây là trường hợp tốt nhất, nhưng nếu một danh sách mà a xuất hiện ở vị trí cuối cùng hoặc a không có trong danh sách, ta cần n lần so sánh a với từng ai (i=1,2,…,n), trường hợp này là trường hợp xấu nhất. Vì vậy, chúng ta cần đưa vào khái niệm thời gian chạy trong trường hợp xấu nhất và thời gian chạy trung bình. Thời gian chạy trong trường hợp xấu nhất (Worst-case running time) của một thuật toán là thời gian chạy lớn nhất của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ. Chúng ta sẽ ký hiệu thời gian chạy trong trường hợp xấu nhất là T(n), trong đó n là cỡ của dữ liệu vào. Sau này khi nói tới thời gian chạy của thuật toán chúng ta cần hiểu đó là thời gian chạy trong trường hợp xấu nhất. Sử dụng thời gian chạy trong trường hợp xấu nhất để biểu thị thời gian chạy của thuật toán có nhiều ưu điểm. Trước hết, nó đảm bảo rằng, thuật toán không khi nào tiêu tốn nhiều thời gian hơn thời gian chạy đó. Hơn nữa, trong các áp dụng, trường hợp xấu nhất cũng thường xuyên xảy ra. Chúng ta xác định thời gian chạy trung bình (Average running time) của thuật toán là số trung bình cộng của thời gian chạy của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ n. Thời gian chạy trung bình của thuật toán sẽ được ký hiệu là Ttb(n). Đánh giá thời gian chạy trung bình của thuật toán là công việc rất khó khăn, cần phải sử dụng các công cụ của xác suất, thống kê và cần phải biết được phân phối xác suất của các dữ liệu vào. Rất khó biết được phân phối xác suất của các dữ liệu vào. Các phân tích thường phải dựa trên giả thiết các dữ liệu vào có phân phối xác suất đều. Do đó, sau này ít khi ta đánh giá thời gian chạy trung bình.Để có thể phân tích đưa ra kết luận về thời gian chạy của thuật toán độc lập với sự cài đặt thuật toán trong một ngôn ngữ lập trình, độc lập với máy tính được sử dụng để thực hiện thuật toán, chúng ta đo thời gian chạy của thuật toán bởi số phép toán sơ cấp cần phải thực hiện khi ta thực hiện thuật toán. Cần chú ý rằng, các phép toán sơ cấp là các phép toán số học, các phép toán logic, các phép toán so sánh,…, nói chung, các phép toán sơ cấp cần được hiểu là các phép toán mà khi thực hiện chỉ đòi hỏi một thời gian cố định nào đó (thời gian này nhiều hay ít là phụ thuộc vào tốc độ của máy tính). Như vậy chúng ta xác định thời gian chạy T(n) là số phép toán sơ cấp mà thuật toán đòi hỏi, khi thực hiện thuật toán trên dữ liệu vào cỡ n. Tính ra biểu thức mô tả hàm T(n) được xác định như trên là không đơn giản, và biểu thức thu được có thể rất phức tạp. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 15 Do đó, chúng ta sẽ chỉ quan tâm tớitốc độ tăng(Rate of growth) của hàm T(n), tức là tốc độ tăng của thời gian chạy khi cỡ dữ liệu vào tăng. Ví dụ, giả sử thời gian chạy của thuật toán là T(n) = 3n2 + 7n + 5 (phép toán sơ cấp). Khi cỡ n tăng, hạng thức 3n2 quyết định tốc độ tăng của hàm T(n), nên ta có thể bỏ qua các hạng thức khác và có thể nói rằng thời gian chạy của thuật toán tỉ lệ với bình phương của cỡ dữ liệu vào. 1.2.1.2 Kí pháp để đánh giá độ phức tạp thuật toán Giả sử T(n) là thời gian thực hiện một thuật toán nào đó và f(n), g(n), h(n) là các hàm xác định dương với mọi n. Khi đó ta có độ phức tạp của thuật toán là: - Hàm Theta lớn:Θ(g(n)) nếu tồn tại các hằng số dương c1 và c2 và n0 sao cho: c1g(n) ≤ T(n) ≤ c2 g(n) và gọi kí pháp chữ Θ theta lớn, hàm g(n) gọi là giới hạn chặt của hàm T(n). - Hàm Omega lớn: Ω(g(n)) nếu tồn tại các hàng số c và n0 sao cho T(n) ≥c.g(n) với mọi n ≥ n0 và gọi là kí pháp chữ Ω lớn, hàm g(n) được gọi là giới hạn dưới của hàm T(n). - Hàm O lớn: O(g(n)) nếu tồn tại các hàng số c và n0 sao cho T(n) ≤c.g(n) với mọi n ≥ n0và gọi là kí pháp chữ O lớn, hàm g(n) được gọi là giới hạn trên của hàm T(n). 1.2.1.3 Các tính chất (i). Tính bắc cầu: Tất cả các kí pháp trên đều có tính bắc cầu. Nếu f(n)=O(g(n)) và g(n)= O(h(n)) thì f(n)= O(h(n)) (ii). Tính phản xạ: Tất cả các kí pháp trên đều có tính phản xạf(n)=O(f(n)) 1.2.2 Xác định độ phức tạp của thuật toán Quy tắc hằng số: Nếu đoạn chương trình P có thời gian thực hiện T(n)= O(c1f(n)) với c1 là một hằng số dương thì có thể coi đoạn chương trình P có độ phức tạp tính toán là O(f(n)). Chứng minh: T(n)= O(c1f(n)) nên tồn tại c0>0 và n0>0 để T(n) ≤ c0.c1 f(n) với mọi n≥ n0.Đặt c=c0.c1 ta có điều cần chứng minh. Quy tắc lấy Max: Nếu đoạn chương trình P có thời gian thực hiện T(n)=O(f(n)+g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(max( f(n), g(n))). Chứng minh: T(n)=O(f(n)+g(n)) nên tồn tại n0>0 và c>0 để T(n) ≤cf(n) + cg(n), với mọi n ≥ n0 vậy T(n) ≤cf(n) +cg(n) ≤ 2cmax (f(n),g(n)) với mọi n ≥ n0. Từ đó suy điều cần chứng minh. Quy tắc cộng: Nếu P1 có thời gian thực hiện là T1(n)=O(f(n)) và P2 có thời gian thực hiện T2(n)=O(g(n)), khi đó: T1(n) +T2(n) = O(f(n) +g(n)). Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 16 Chứng minh: Vì T1(n)=O(f(n)) nên tồn tại các hàng số c1 và n1 sao cho T(n) ≤ c1.f(n) với mọi n ≥ n1. Vì T2(n)=O(g(n)) nên tồn tại các hàng số c2 và n2 sao cho T(n) ≤ c1.g(n) với mọi n ≥ n2. Chọn c=max (c1,c2) và n0=max (n1,n2) ta có với mọi n ≥ n0: T(n)=T1(n) + T2(n) ≤ c1f(n) + c2g(n) ≤ cf(n) +cg(n) = c(f(n) +g(n)). Như vậy ta có điều cần chứng minh. Quy tắc nhân:Nếu đoạn chương trình P có thời gian thực hiện T(n)=O(f(n)). Khi đó nếu thực hiện k(n) lần đoạn chương trình P với k(n)=O(g(n)) thì độ phức tạp tính toán sẽ là: O(f(n) g(n)). Chứng minh: Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n)*T(n), theo định nghĩa: - Tồn tại ck≥ 0 và nk>0 để k(n) ≤ ck(g(n)) với mọi n ≥ nk - Tồn tại cT≥ 0 và nT>0 để T(n) ≤ cTf(n) với mọi n ≥ nT Vậy với mọi n ≥ max(nT,nk)ta có k(n)T(n) ≤ ckcT(f(n)g(n)). Từ đó suy ra điều cần chứng minh. 1.2.3 Ký hiệu Big-O và biểu diễn thời gian chạy của thuật toán 1.2.3.1 Định nghĩa ký hiệu Big-O Bây giờ chúng ta đưa ra định nghĩa khái niệm một hàm là “ô lớn” của một hàm khác. Định nghĩa. Giả sử f(n) và g(n) là các hàm thực không âm của đối số nguyên không âm n. Ta nói “f(n) là ô lớn của g(n)” và viết là f(n)=O( g(n) ) nếu tồn tại các hằng số dương c và n0 sao cho f(n) ≤ cg(n) với mọi n ≥ n0.[2] Như vậy, f(n)=O(g(n)) có nghĩa là hàm f(n) bị chặn trên bởi hàm g(n) với một nhân tử hằng nào đó khi n đủ lớn. Muốn chứng minh được f(n)=O(g(n)), chúng ta cần chỉ ra nhân tử hằng c , số nguyên dương n0 và chứng minh được f(n) ≤ cg(n) với mọi n ≥ no . Ví dụ. Giả sử f(n) = 5n3 + 2n2 + 13n + 6, ta có: f(n) = 5n3 + 2n2 + 13n + 6 ≤ 5n3 + 2n3 + 13n3 + 6n3 = 26n3 Bất đẳng thức trên đúng với mọi n≥ 1, và ta có n0=1, c=26. Do đó, ta có thể nói f(n)=O(n3). Tổng quát nếu f(n) là một đa thức bậc k của n: f(n) = aknk+ ak-1nk-1 + ... + a1n + a0 thì f(n)=O(nk) Sau đây chúng ta đưa ra một số hệ quả từ định nghĩa ký hiệu ô lớn, nó giúp chúng ta hiểu rõ bản chất ký hiệu ô lớn. (Lưu ý, các hàm mà ta nói tới đều là các hàm thực không âm của đối số nguyên dương) - Nếu f(n) = g(n) + g1(n) + ... + gk(n), trong đó các hàm gi(n) (i=1,...,k) tăng chậm hơn hàm g(n) (tức là gi(n)/g(n) 0, khi n 0) thì f(n) = O(g(n)) Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 17 - Nếu f(n)=O(g(n)) thì f(n)=O(d.g(n)), trong đó d là hằng số dương bất kỳ - Nếu f(n)=O(g(n)) và g(n)=O(h(n)) thì f(n)=O(h(n)) (tính bắc cầu) Các kết luận trên dễ dàng được chứng minh dựa vào định nghĩa của ký hiệu ô lớn. Đến đây, ta thấy rằng, chẳng hạn nếu f(n)=O(n2) thì f(n)=O(75n2), f(n)=O(0,01n2), f(n)=O(n2 + 7n + logn), f(n)=O(n3),..., tức là có vô số hàm là cận trên (với một nhân tử hằng nào đó) của hàm f(n). Một nhận xét quan trọng nữa là, ký hiệu O(g(n)) xác định một tập hợp vô hạn các hàm bị chặn trên bởi hàm g(n), cho nên ta viết f(n)=O(g(n)) chỉ có nghĩa f(n) là một trong các hàm đó. 1.2.3.2 Biểu diễn thời gian chạy của thuật toán Thời gian chạy của thuật toán là một hàm của cỡ dữ liệu vào: hàm T(n). Chúng ta sẽ biểu diễn thời gian chạy của thuật toán bởi ký hiệu ô lớn: T(n)=O(f(n)), biểu diễn này có nghĩa là thời gian chạy T(n) bị chặn trên bởi hàm f(n). Thế nhưng như ta đã nhận xét, một hàm có vô số cận trên. Trong số các cận trên của thời gian chạy, chúng ta sẽ lấy cận trên chặt (Tight bound) để biểu diễn thời gian chạy của thuật toán. Định nghĩa. Ta nói f(n) là cận trên chặt của T(n) nếu T(n)=O(f(n)), và nếu T(n)=O(g(n)) thì f(n)=O(g(n)). Nói một cách khác, f(n) là cận trên chặt của T(n) nếu nó là cận trên của T(n) và ta không thể tìm được một hàm g(n) là cận trên của T(n) mà lại tăng chậm hơn hàm f(n). Sau này khi nói thời gian chạy của thuật toán là O(f(n)), chúng ta cần hiểu f(n) là cận trên chặt của thời gian chạy. Nếu T(n)=O(1) thì điều này có nghĩa là thời gian chạy của thuật toán bị chặn trên bởi một hằng số nào đó, và ta thường nói thuật toán có thời gian chạy hằng. Nếu T(n)=O(n), thì thời gian chạy của thuật toán bị chặn trên bởi hàm tuyến tính, và do đó ta nói thời gian chạy của thuật toán là tuyến tính. Các cấp độ thời gian chạy của thuật toán và tên gọi của chúng được liệt kê trong bảng sau: Bảng 1.3Các lớp độ phức tạp tính toán Ký hiệu O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) Số hóa bởi Trung tâm Học liệu Tên gọi hằng logarit tuyến tính nlogn bình phương lập phương mũ http://www.lrc-tnu.edu.vn/ 18 Hằng số: Hầu hết các chỉ thị của các chương trình đều được thực hiện một lần hay nhiều nhất chỉ một vài lần. Nếu tất cả các chỉ thị của cùng một chương trình có tính chất này thì chúng ta sẽ nói rằng thời gian chạy của nó là hằng số. Điều này hiển nhiên là điều mà ta phấn đấu để đạt được trong việc thiết kế thuật toán. LogN: Khi thời gian chạy của chương trình là logarit tức là thời gian chạy chương trình tiến chậm khi N lớn dần. Thời gian chạy thuộc loại này xuất hiện trong các chương trình mà giải một bài toán lớn bằng cách chuyển nó thành một bài toán nhỏ hơn, bằng cách cắt bớt kích thước một hằng số nào đó. Với mục đích của chúng ta, thời gian chạy có được xem như nhỏ hơn một hằng số “lớn“. Cơ số của logarit làm thay đổi hằng số đó nhưng không nhiều: Khi N là 1000 thì logN là 3 nếu cơ số là 10, là 10 nếu cơ số là 2; khi N là một triệu, logN được nhân gấp đôi. bất cứ khi nào N được nhân đôi, logN tăng lên thêm một hằng số. N: Khi thời gian chạy của một chương trình là tuyến tính, nói chung đây là trường hợp mà một số lượng nhỏ các xử lý được làm cho mỗi phần tử dữ liệu nhập. Khi N là một triệu thì thời gian chạy cũng cỡ như vậy. Khi N được nhân gấp đôi thì thời gian chạy cũng được nhân gấp đôi. Đây là tình huống tối ưu cho một thuật toán mà phải xử lý N dữ liệu nhập (hay sản sinh ra N dữ liệu xuất). NlogN: Đây là thời gian chạy tăng dần lên cho các thuật toán mà giải một bài toán bằng cách tách nó thành các bài toán con nhỏ hơn, kế đến giải quyết chúng một cách độc lập và sau đó tổ hợp các lời giải. Chúng ta nói rằng thời gian chạy của thuật toán như thế là “NlogN”. N2: Khi thời gian chạy của một thuật toán là bậc hai, trường hợp này chỉ có ý nghĩa thực tế cho các bài toán tương đối nhỏ. Thời gian bình phương thường tăng dần lên trong các thuật toán mà xử lý tất cả các phần tử dữ liệu (có thể là hai vòng lặp lồng nhau). Khi N là một ngàn thì thời gian chạy là 1 triệu. Khi N được nhân đôi thì thời gian chạy tăng lên gấp 4 lần. N3: Tương tự, một thuật toán mà xử lý các bộ ba của các phần tử dữ liệu (có thể là 3 vòng lặp lồng nhau) có thời gian chạy bậc ba và cũng chí ý nghĩa thực tế trong các bài toán nhỏ. Khi N là một trăm thì thời gian chạy là một triệu. Khi N được nhân đôi thì thời gian chạy tăng lên gấp 8 lần. 2N: Một số ít thuật toán có thời gian chạy lũy thừa lại thích hợp trong một số trường hợp thực tế. Khi N là hai mươi thì thời gian chạy là 1 triệu. Khi N tăng gấp đôi thì thời gian chạy được nâng lên luỹ thừa hai Đối với một thuật toán, chúng ta sẽ đánh giá thời gian chạy của nó thuộc cấp độ nào trong các cấp độ đã liệt kê trên. Trong bảng trên, chúng ta đã sắp xếp các cấp độ thời gian chạy theo thứ tự tăng dần, chẳng hạn thuật toán có thời gian chạy là O(logn) chạy nhanh hơn thuật toán có thời gian chạy là O(n),...Các thuật toán có thời gian chạy là O(nk), với Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 19 k=1,2,3,..., được gọi là các thuật toán thời gian chạy đa thức (Polynomial-time algorithm). Để so sánh thời gian chạy của các thuật toán thời gian đa thức và các thuật toán thời gian mũ, chúng ta hãy xem xét bảng sau: Bảng 1.4Thời gian chạy của các lớp thuật toán Thời gian chạy n n2 n3 n5 2n 3n Cỡ dữ liệu vào 10 0,00001 giây 0,0001 giây 0,001 giây 0,1 giây 0,001 giây 0,059 giây 20 0,00002 giây 0,0004 giây 0,008 giây 3,2 giây 1,0 giây 58 phút 30 40 50 60 0,00003 giây 0,0009 giây 0,027 giây 24,3 giây 17,9 phút 6,5 năm 0,00004 giây 0,0016 giây 0,064 giây 1,7 phút 12,7 ngày 3855 thế kỷ 0,00005 giây 0,0025 giây 0,125 giây 5,2 phút 35,7 năm 2.108 thế kỷ 0,00006 giây 0,0036 giây 0,216 giây 13 phút 366 thế kỷ 1,3. 1013 thế kỷ Trong bảng trên, giả sử mỗi phép toán sơ cấp cần 1 micro giây để thực hiện. Thuật toán có thời gian chạy n2, với cỡ dữ liệu vào n=20 thì thời gian chạy là 202x10-6 =0,004 giây. Đối với thuật toán hàm mũ, thời gian chạy là chấp nhận được chỉ với các dữ liệu vào có cỡ rất khiêm tốn, n < 30; khi cỡ dữ liệu vào tăng, thời gian chạy sẽ tăng lên rất nhanh và trở thành con số khổng lồ. Chẳng hạn, thuật toán với thời gian chạy 3n, với dữ liệu vào cỡ 60, nó đòi hỏi thời gian là 1,3x1013 thế kỉ! Vì vậy nghiên cứu tìm ra các thuật toán hiệu quả (chạy nhanh) cho các vấn đề có nhiều ứng dụng trong thực tiễn luôn luôn là sự mong muốn của các nhà tin học. 1.2.4 Độ phức tạp thuật toán với tình trạng dữ liệu vào Trong nhiều trường hợp, thời gian thực hiện giải thuật không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng của dữ liệu. Chẳng hạn thời gian sắp xếp một dãy số theo thứ tự tăng dần mà dãy đưa vào chưa có thứ tự sẽ khác với thời gian sắp xếp một dãy số đã sắp xếp rồi hoặc đã sắp xếp theo thứ tự ngược lại. Lúc này, khi phân tích thời gian thực hiện giải thuật ta sẽ phải xét tới trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất. Khó khăn trong việc xác định độ phức tạp tính toán trong trường hợp trung bình (bởi việc xác định T(n) trung bình thường phải dùng tới những công cụ toán phức tạp), nên ta thường đánh giá độ phức tạp tính toán trong trường hợp xấu nhất. 1.2.5 Chi phí thực hiện thuật toán Độ phức tạp tính toán đặt ra là để đánh giá chi phí thực hiện một giải thuật về mặt thời gian. Nhưng chi phí thực hiện giải thuật còn có rất nhiều yếu tố khác nữa: không gian bộ nhớ phải sử dụng là một ví dụ. Tuy nhiên, trên phương diện phân tích lý thuyết, ta chỉ có thể xét tới vấn đề thời gian bởi việc xác định các chi phí khác nhiều khi rất mơ hồvà phức tạp. Đối với người lập trình thì khác, một thuật toán với độ phức tạp dù rất thấp cũng sẽ là vô dụng nếu như không thể cài đặt được trên máy tính, chính vì vậy khi bắt tay cài đặt một thuật toán, ta phải biết cách tổ chức dữ liệu một cách khoa học, tránh lãng phí bộ Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 20 nhớ không cần thiết. Có một quy luật tương đối khi tổ chức dữ liệu: Tiết kiệm được bộ nhớ thì thời gian thực hiện thường sẽ chậm hơn và ngược lại. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/