ĐỒ ÁN NHẬP MÔN PHÂN TÍCH ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

Tải bản đầy đủ (.doc) (31 trang)

1. Trang chủ
>>
2. Giáo án - Bài giảng
>>
3. Tin học

ĐỒ ÁN NHẬP MÔN PHÂN TÍCH ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (513.69 KB, 31 trang )

BỘ MÔN KHOA HỌC MÁY TÍNH…………………………………………………………Đồ án Nhập Môn Phân Tích Độ Phức Tạp Thuật ToánĐề tài: Đánh giá các thuật toán SortGiảng viên hướng dẫn lý thuyếtTS. Trần Đan ThưGiảng viên hướng dẫn thực hànhDương Chí NhânNhóm thực hiện0712002 – Nguyễn Thanh Đồng0712228 – Trần Trung Kiên 0712394 – Bành Trí Thành0712474 – Nguyễn Trọng Nhật Trung0712476 – Phan Thanh TríTP.HCM, tháng 05 năm 2010MỞ ĐẦUĐề tài nhóm chúng tôi là đánh giá độ phức tạp của các giải thuật sắp xếp. Nói đến các giải thuật sắp xếp thì có lẽ đây là một chủ đề đã quá quen thuộc và kinh điển. Tuy nhiên, vì chúng ta xem nó quá quen thuộc nên chúng ta thường hay quên nó đi. Mục tiêu của đề tài này là để chúng ta cùng nhau nắm lại tư tưởng của các thuật toán sắp xếp, độ phức tạp về mặt lý thuyết, và hơn nữa, bằng thực nghiệm đánh giá, kiểm chứng lại các độ phức tạp này. Nội dung của phần báo cáo được chia làm 2 phần lớn: Nền tảng lý thuyết: Giới thiệu tổng quan về tư tưởng, độ phức tạp của các thuật toán sắp xếp. Thực nghiệm: Nêu lên cách tiến hành thực nghiệm, kết quả và nhận xét.Các thuật toán SortPage 2MỤC LỤC MỞ ĐẦU 2 MỤC LỤC 3Chương 1 NỀN TẢNG LÝ THUYẾT 41.1 SELECTION SORT 51.1.1 Ý tưởng thuật toán 51.1.2 Ví dụ minh họa 51.1.3 Độ phức tạp 61.2 INTERCHANGE SORT 71.2.1 Ý tưởng thuật toán 71.2.2 Ví dụ minh họa 81.2.3 Độ phức tạp 111.3 BUBBLE SORT 121.3.1 Ý tưởng thuật toán 121.3.2 Ví dụ minh họa 12 Cho dãy số như trên thuật toán SELECTION SORT 121.3.3 Độ phức tạp 131.4 SHAKER SORT 141.4.1 Ý tưởng thuật toán 141.4.2 Ví dụ minh họa 141.4.3 Độ phức tạp 141.5 INSERTION SORT 141.5.1 Ý tưởng thuật toán 141.5.2 Ví dụ minh họa 151.5.3 Độ phức tạp 161.6 BINARY INSERTION SORT 171.6.1 Ý tưởng thuật toán 171.6.2 Ví dụ minh họa 171.6.3 Độ phức tạp 171.7 HEAP SORT 181.7.1 Ý tưởng thuật toán 18Các thuật toán SortPage 31.7.2 Ví dụ minh họa 181.7.3 Độ phức tạp 201.8 MERGE SORT 211.8.1 Ý tưởng thuật toán 211.8.2 Ví dụ minh họa 211.8.3 Độ phức tạp 221.9 BINARY TREE 231.9.1 Ý tưởng thuật toán 231.9.2 Ví dụ minh họa 231.9.3 Độ phức tạp 261.10 QUICK SORT 271.10.1 Ý tưởng thuật toán 271.10.2 Ví dụ minh họa 271.10.3 Độ phức tạp 281.11 SHELL SORT 291.11.1 Ý tưởng thuật toán 291.11.2 Ví dụ minh họa 291.11.3 Độ phức tạp 30Chương 2 THỰC NGHIỆM 312.1 PHÂN TÍCH VÀ THIẾT KẾ CHƯƠNG TRÌNH THỰC NGHIỆM 312.2 KẾT QUẢ THỰC NGHIỆM 31Chương 3 ĐÁNH GIÁ ĐỀ TÀI 31 TÀI LIỆU THAM KHẢO 31Chương 1 NỀN TẢNG LÝ THUYẾTCác thuật toán SortPage 41.1 SELECTION SORT1.1.1 Ý tưởng thuật toán Ta chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về đầu dãy hiện hành. Sau đó, ta không quan tâm đến nó nữa, ta xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu tính từ vị trí thứ 2. Cứ vậy, cho đến khi dãy hiện hành chỉ còn 1 phần tử, ta được 1 dãy sắp tăng. Các bước tiến hành như sau:o Bước 1: Khởi động i = 1o Bước 2: Tìm phần tử nhỏ nhất a[min] trong dãy hiện hành từ a[i] đến a[N]o Bước 3: Hoán vị a[min] và a[i]o Bước 4: i = i+1 Nếu i < =N-1: quay trở lại bước 2 Ngược lại: STOP!1.1.2 Ví dụ minh họaCho dãy số 1 2 8 5 12 6 4 15 Hình minh họa cho quá trình sắp xếp của dãy số trên:Các thuật toán SortPage 51.1.3 Độ phức tạpĐể chọn được phần tử nhỏ nhất, ta cần duyệt qua n phần tử (tốn n-1 phép so sánh) và sau đó hoán vị nó với phần tử đầu tiên của dãy hiện hành. Để tìm phần tử nhỏ nhất tiếp theo, ta cần duyệt qua n-1 phần tử (tốn n-2 phép so sánh). Cứ như vậy, ta thấy ngay thuật toán sẽ tốn (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) phép so sánh. Các thuật toán SortPage 6D Dãy được sắp xếp tăngMỗi lần duyệt, ta luôn phải hoán vị 1 lần (1 hoán vị tương đương với 3 phép gán), nghĩa là thuật toán sẽ tốn 3(n-1) + 3(n-2) + … + 3 = 3n(n-1)/2 = O(n2) phép gán.Tổng kết lại, ta luôn có độ phức tạp của thuật toán Selection Sort thuộc O(n2) trong mọi trường hợp.1.2 INTERCHANGE SORT1.2.1 Ý tưởng thuật toán Ý tưởng chính của thuật toán này là ta tìm các cặp nghịch thế và triệt tiêu chúng. Ta xuất phát từ phần tử đầu tiên của dãy, tìm tất các các cặp nghịch thế chứa phần tử này, triệt tiêu chúng bằng các hoán vị phần tử này với phần tử tương ứng trong cặp nghịch thế. Ta dễ nhận thấy sau lần duyệt đầu tiên, phần tử đầu tiên chính là phần tử nhỏ nhất của dãy. Ta tiếp tục xử lý với phần tử thứ hai, ta có được phần tử thứ hai chính là phần tử nhỏ thứ hai của dãy. Cứ như vậy, sau khi xử lý với phần tử thứ N -1 của dãy, ta được một dãy sắp tăng. Các bước tiến hành như sau:o Bước 1: Khởi động i = 1o Bước 2: j = i+1o Bước 3: Trong khi j <= N thực hiện: Nếu a[i]>a[j]: Hoán vị a[i] và a[j] j = j+1 o Bước 4: i = i+1 Nếu i <= N-1: quay trở lại bước 2 Ngược lại: STOP!Các thuật toán SortPage 71.2.2 Ví dụ minh họaCho dãy số : 12 2 8 5 1 6 4 15Hình minh họa cho quá trình sắp xếp của dãy số trên:Các thuật toán SortPage 8Các thuật toán SortPage 9Các thuật toán SortPage 101.2.3 Độ phức tạp Thấy ngay số phép so sánh là luôn không đổi, tức không phụ thuộc vào tình trạng ban đầu của dãy. Ta có thể ước lượng số phép so sánh bằng (n-1) + (n-2) + … + 1 = n(n-1)/2 (phần tử thứ i được so sánh với n-i phần tử còn lại.) Số phép hoán vị (tương đương 3 phép gán) lại phụ thuộc vào tình trạng ban đầu của dãy. Cụ thể như sau:o Trường hợp tốt nhất: Dãy ban đầu đã có thứ tự. Ta thấy ngay ta không tốn một phép hoán vị nào.o Trường hợp xấu nhất: Dãy ban đầu có thứ tự ngược. Ta thấy ngay mỗi lần so sánh phần tử thứ i với n-i phần tử còn lại, ta đều phải thực hiện hoán vị. Điều này có nghĩa là số phép hoán vị bằng n(n-1)/2.Tổng kết lại, ta có độ phức tạp của Interchange Sort thuộc O(n2) trong mọi trường hợp.Các thuật toán SortPage 11D Dãy được sắp xếp tăng1.3 BUBBLE SORT1.3.1 Ý tưởng thuật toán Xét từ đáy và phần tử nhẹ nổi lên trên. Các bước thực hiện:o Bước 1: Khởi động i = 1o Bước 2: j = N //Duyệt từ cuối dãy về vị trí iTrong khi j>i thực hiện: Nếu a[j]<a[j-1]: hoán vị a[j], a[j-1] j = j - 1o Bước 3: i = i + 1 Nếu i <= N-1: quay trở lại bước 2. Ngược lại: STOP!1.3.2 Ví dụ minh họaCho dãy số như trên thuật toán SELECTION SORT1 2 4 12 5 8 6 5Hình minh họa quá trình sắp xếp của thuật toán:Các thuật toán SortPage 121.3.3 Độ phức tạp Thấy ngay số phép so sánh là luôn không đổi, tức không phụ thuộc vào tình trạng ban đầu của dãy. Với i bất kỳ, ta luôn phải so sánh V[j] với V[j-1], mà j chạy từ n đến i+1, tức ta tốn n-i phép so sánh. Thêm nữa, i chạy từ 1 đến n-1. Vậy ta tính được số phép so sánh tổng cộng: ∑(n-i) với i chạy từ 1 đến n-1 = (n-1) + (n-2) + … + 1 = n(n-1)/2. Số phép hoán vị (tương đương 3 phép gán) lại phụ thuộc vào tình trạng ban đầu của dãy. Cụ thể như sau:Các thuật toán SortPage 13D Dãy được sắp xếp tăngo Trường hợp tốt nhất: Dãy ban đầu đã có thứ tự. Ta thấy ngay ta không tốn một phép hoán vị nào.o Trường hợp xấu nhất: Dãy ban đầu có thứ tự ngược. Xét i bất kỳ, ta thấy rằng mỗi lần so sánh a[j] với a[j-1], ta đều phải thực hiện hoán vị. Điều này có nghĩa là số phép hoán vị bằng n(n-1)/2.Tổng kết lại, ta có độ phức tạp của Bubble Sort thuộc O(n2) trong mọi trường hợp.1.4 SHAKER SORT1.4.1 Ý tưởng thuật toán Đây là thuật toán cải tiến từ thuật toán Bubble Sort Ta thấy ở mỗi lượt duyệt phần tử nhẹ nổi lên rất nhanh, còn phần tử nặng chìm xuống rất chậm, nên ta sẽ cải tiến thêm 1 chiều duyệt ngược lại để phần từ nặng chìm nhanh hơn. Từ vị trí đổi chỗ cuối cùng đến đầu dãy đã được sắp xếp, cho nên cần thêm 1 biến lưu vị trí đổi chỗ cuối cùng để tăng tốc độ.1.4.2 Ví dụ minh họa1.4.3 Độ phức tạp Ta thấy sự chuyển dời của phần tử không có gì là cải tiến (từ vị trí ban đầu của nó, để đi đến vị trí đúng đều mất chi phí như Bubble Sort). Chỉ có số phép so sánh là được cải tiến, nhưng chưa tìm được công thức tính số phép so sánh, mặt khác ta thấy chi phí chuyển dời luôn cao hơn (Chi phí hoán vị thường mất 3 phép gán) so sánh nên cải tiến có thể xem như không đáng kể. Thuật toán vẫn được xếp ở O(n2).1.5 INSERTION SORT1.5.1 Ý tưởng thuật toán Giả sử ta có dãy a1, a2, …, an trong đó i phần tử đầu tiên a1, a2, …, ai đã có thứ tự. Ý tưởng của thuật toán là tìm vị trị thích hợp và chèn phần tử ai+1 vào dãy đã có thứ tự trên để có được một dãy mới có thứ tự. Cứ thế, làm đến cuối dãy ta sẽ được một dãy có thứ tự.Các thuật toán SortPage 14 Với dãy ban đầu a1, a2, …, an ta có thể coi đoạn chỉ có một phần tử a1 là một đoạn đã có thứ tự, sau đó ta chèn phần tử a2 vào dãy a1 để có dãy a1a2 có thứ tự. Tiếp đó, ta lại chèn phần tử a3 vào dãy a1a2 để có dãy a1a2a3 có thứ tự. Cứ thế, đến cuối cùng ta chèn phần tử an vào dãy a1a2…an-1 ta sẽ được dãy a1a2…an có thứ tự. Các bước thực hiện:o Bước 1: Khởi động với i = 2 //Đoạn a[1] đã được sắpo Bước 2: x = a[i]. Tìm vị trí thích hợp pos trong đoạn a[1]…a[i-1] để chèn x vàoo Bước 3: Dời đoạn a[pos]…a[i-1] sang phải để có chỗ đưa x vào.o Bước 4: a[pos] = xo Bước 5: i = i + 1 Nếu i<=n: quay lại bước 2. Ngược lại: STOP!1.5.2 Ví dụ minh họaCho dãy số a: 12 2 8 5 1 6 4 15Các thuật toán SortPage 151.5.3 Độ phức tạp Ta thấy các phép so sánh xảy ra trong vòng lặp nhằm tìm vị trí thích hợp pos để chèn x. Mỗi lần so sánh mà thấy vị trí đang xét không thích hợp, ta dời phần tử a[pos] sang phải. Ta cũng thấy số phép gán và số phép so sánh của thuật toán phụ thuộc vào tình trạng của dãy ban đầu. Do đó ta chỉ có thể ước lượng như sau:o Trường hợp tốt nhất: dãy ban đầu đã có thứ tự. Ta tìm được ngay vị trí thích hợp để chèn ngay lần so sánh đầu tiên mà không cần phải vô vòng lặp. Như vậy, với i chạy từ 2 đến n thì số phép so sánh tổng cộng sẽ là n-1. Còn với số phép gán, do thuật toán không chạy vào vòng lặp nên xét i Các thuật toán SortPage 16bất kỳ, ta luôn chỉ phải tốn 2 phép gán(x = a[i] và a[pos] = x). Từ đây, ta tính được số phép gán tổng cộng bằng 2(n - 1).o Trường hợp xấu nhất: dãy ban đầu có thứ tự ngược. Ta thấy ngay vị trí thích hợp pos luôn là vị trí đầu tiên của dãy đã có thứ tự, và do đó, để tìm ra vị trí này ta phải duyệt hết dãy đã có thứ tự. Xét i bất kỳ, ta có số phép so sánh là i-1, số phép gán là (i - 1) + 2 = i + 1. Với i chạy từ 2 đến n, ta tính được số phép so sánh tổng cộng bằng 1 + 2 + … + (n - 1) = n(n - 1)/2 và số phép gán bằng 3 + 4 + + (n + 1) = (n + 4)(n - 1)/2Tổng kết lại, ta có độ phức tạp của Insertion Sort như sau:o Trường hợp tốt nhất: O(n)o Trường hợp xấu nhất O(n2)1.6 BINARY INSERTION SORT1.6.1 Ý tưởng thuật toán Đây là thuật toán cải tiến từ Insertion Sort, ta nhận thấy chi phí tìm kiếm vị trí thích hợp để chèn phần tử của Insertion là tuyến tính n, nên thuật toán này sẽ dùng cách tìm nhị phân để giảm số phép so sánh cho việc tìm kiếm còn log2n.1.6.2 Ví dụ minh họa1.6.3 Độ phức tạp Ta nhận thấy rằng cải tiến của thuật toán chỉ giúp việc tìm kiếm nhanh hơn, giảm đi chi phí so sánh trong lúc tìm kiếm, còn chi phí cho việc chèn vẫn không thay đổi (vẫn phải dịch đúng k phần tử như Insertion Sort để chèn) nên chi phí phép gán không có cải tiến. Tìm kiếm tốt nhất khi vừa tìm phần tử lần đầu là ra ngay, phần tử đó sẽ nằm ở vị trí middle của dãy đã có thứ tự, nhưng chi phí chèn lúc này sẽ là n/2, với chi phí này còn cao so với trường hợp tốt nhất. Thuật toán chỉ tốt nhất khi chi phí chèn là 1, ứng với phần tử tìm phải nằm ở cuối dãy có thứ tự, chi phí tìm lúc này là log2n, mà ta phải làm n lần cho n phần tử nên là O(nlogn)Các thuật toán SortPage 17 Thuật toán xấu nhất khi phần tử tìm được nằm ở đầu dãy, chi phí chèn lúc này là n (tìm kiếm là log2n, nhưng chi phí chèn mạnh hơn), mà có n phần tử nên là O(n2). Ta thấy dường như độ phức tạp thuật toán phụ thuộc mạnh vào chi phí chèn hơn là tìm kiếm, cho nên cách tốt hơn ta sẽ cài đặt bằng danh sách liên kết để việc chèn được tốt hơn. Độ phức tạp thuật toán như sau:o Trường hợp tốt nhất: O(nlogn)o Trường hợp xấu nhất O(n2)1.7 HEAP SORT1.7.1 Ý tưởng thuật toán Định nghĩa Heap: Heap là mảng 1 chiều chứa các phần tử từ a1, a2 … an. Các phần tử từ a[n/2 + 1] đến a[n] là heap tự nhiên. Các phần tử còn lại thỏa a[i] >= a[2*i] và a[i] >= a[2*i+1] (i=1…n/2) (Điều kiện này là cho sắp xếp tăng dần). Như vậy ta thấy gốc của heap luôn là phần tử lớn nhất, nếu ta lần lượt rút trích phần tử gốc và xây dựng lại heap đã bị rút trích ta sẽ có một mảng có thứ tự tăng dần. Giải thuật:o Bước 1: Xây dựng heap từ mảng ban đầu.o Bước 2: Hoán vị phần tử đầu và cuối mảng, rồi giảm dần số phần tử của mảng xuống thành n-1 (bỏ phần tử cuối).o Bước 3: Tiếp tục xây dựng và hoán vị như trên cho đến hết ta sẽ có dãy được sắp thứ tự tăng dần (muốn sắp giảm dần ta chi cần cho phần tử gốc của heap là phần tử nhỏ nhất).1.7.2 Ví dụ minh họaCho dãy số a:12 2 8 5 1 6 4 15Giai đoạn 1: hiệu chỉnh dãy ban đầu thành heapCác thuật toán SortPage 18Giai đoạn 2: Sắp xếp dãy số dựa trên heap:Các thuật toán SortPage 19Thực hiện tương tự cho r = 5, 4, 3, 2 ta được:1.7.3 Độ phức tạp Ta thấy được chi phí cho xây dựng heap khi thêm vào heap một phần tử mới là log2n (chính là chiều cao heap cho mỗi lần làm chìm phần tử xuống vị trí thích hợp), mặt khác từ bước 2 đến bước 3 ứng với mỗi phần tử ta sẽ xây dựng lại heap một lần, mà ta có n phần tử. Vậy ta có thể ước tính chi phí cho sắp xếp HeapSort là O(nlogn) cho mọi trường hợp. (Từ thực nghiệm cài đặt cho kết quả là ~ 4log2n)Các thuật toán SortPage 201.8 MERGE SORT1.8.1 Ý tưởng thuật toán Cho dãy ban đầu a1, a2, …, an. Ta luôn có thể coi nó là tập hợp liên tiếp của các dãy có thứ tự. Ta gọi các dãy có thứ tự này là các dãy con. Trong phương pháp Merge Sort, vấn đề là ta tìm cách phân hoạch dãy ban đầu thành các dãy con. Sau khi phân hoạch xong, dãy ban đầu sẽ được tách thành hai dãy phụ theo nguyên tắc phân phối luân phiên dãy con. Sau đó, ta trộn từng cặp dãy con của hai dãy phụ thành một dãy con của dãy ban đầu. Ta nhận thấy số dãy con của dãy ban đầu lúc này giảm đi ít nhất là một nửa. Cứ thế sau một số bước, ta sẽ nhận được dãy ban đầu với số dãy con bằng 1, có nghĩa là ta đã sắp xếp xong. Trộn trực tiếp: đây là phương pháp trộn đơn giản nhất. Việc phân hoạch dãy ban đầu đơn giản như sau: Với dãy ban đầu có n phân tử, ta cứ phân hoạch thành n dãy con. Vì rằng mỗi dãy con chỉ có 1 phần tử nên nó là dãy có thứ tự. Cứ mỗi lần tách – trộn, chiều dài của dãy con sẽ được nhân đôi. Các bước tiến hành:o Bước 1: Khởi động k = 1 //Với k là chiều dài dãy cono Bước 2: Phân phối dãy a = a1, a2, …, an vào hai dãy phụ b, c theo nguyên tắc phân phối luân phiên từng dãy con.b = a1, …, ak, a2k+1, …, a3k, …c = ak+1, …, a2k, a3k+1, …, a4ko Bước 3: Từ 2 dãy phụ b, c, ta trộn từng cặp dãy con và đưa vào dãy a.o Bước 4: k = k*2 Nếu k<n: quay lại bước 2. Ngược lại: STOP!1.8.2 Ví dụ minh họaCho dãy số a:12 2 8 5 1 6 4 15Các thuật toán SortPage 21k = 1: k = 2:k = 4:1.8.3 Độ phức tạp Ta thấy ngay số lần lặp của bước 2(phân phối) và bước 3(trộn) bằng log2n. Ta cũng thấy rằng chi phí thực hiện bước 2 và bước 3 tỉ lệ thuận với n. Như vậy, ta có thể ước tính chi phí thực hiện của giải thuật Merge Sort thuộc O(nlog2n). Ta nhận thấy rằng giải thuật làm việc một cách cứng nhắc, không tận dụng được tính thứ tự một phần của dãy ban đầu. Do đó, trong mọi trường hợp độ phức tạp là như nhau. Đây là một nhược điểm của phương pháp trộn trực tiếp.Các thuật toán SortPage 221.9 BINARY TREE1.9.1 Ý tưởng thuật toán Việc sắp xếp trên cây nhị phân tìm kiếm được gói gọn xử lí trong 2 công việc là chèn các khóa mới vào trong cây và duyệt cây nhị phân theo thứ tự LNR. Chèn một khóa mới vào trong cây nhị phân tìm kiếm: phép chèn bắt đầu giống như phép tìm kiếm. Nếu khóa của nút gốc khác khóa cần chèn ta tìm nó trong cây con trái hoặc phải. Nếu cây con trái hoặc phải tương ứng là rỗng (không tìm thấy) thì thêm một nút và gán cho nút ấy khóa cần chèn.void InsertNode(struct node *&treeNode,struct node *newNode){ if (treeNode == NULL) treeNode = newNode; else if (newNode->value < treeNode->value) InsertNode(treeNode->left, newNode); else InsertNode(treeNode->right, newNode);} Duyệt cây nhị phân tìm kiếm : sau khi đã hoàn thành việc tạo dựng một cây nhị phân tìm kiếm. Các nút có thể được duyệt theo thứ tự bằng cách gọi đệ quy cây con bên trái, in nút đang duyệt, rồi duyệt đệ qui cây con bên phải, tiếp tục làm như vây với mỗi nút của cây trong quá trình đệ qui (theo thứ tự LNR). if node == NULL return traverse_binary_tree(node->leftChild, callback); callback(node->value); traverse_binary_tree(node->rightChild, callback);1.9.2 Ví dụ minh họaDuyệt cây theo thứ tự LNR : Cho một cây như sau : Các thuật toán SortPage 23Thứ tự của phép duyệt LNR : CBEDFAKHLVí dụ cụ thể : Cho dãy sau : 44 55 12 42 94 18 6 67Khi insert vào cây ta sẽ được như sau : + Bước 1 : + Bước 2 : + Bước 3 : Các thuật toán SortPage 24 + Bước 4 : + Bước 5 : + Bước 6 : + Bước 7 : Các thuật toán SortPage 25

Trích đoạn

• SHELL SORT

Tài liệu liên quan

• THUẬT TOÁN – ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
  • 28
  • 1
  • 8
• Rèn luyện khả năng đánh giá độ phức tạp của thuật toán
  • 3
  • 1
  • 15
• CÁC KHÁI NIỆM CĂN BẢN VỀ PHÂN TÍCH ĐỘ PHỨC TẠP GIẢI THUẬT
  • 22
  • 675
  • 0
• TÌM HIỂU VÀ TÍNH ĐỘ PHỨC TẠP CỦA THUẬT TOÁN DFS (Depth First Search)
  • 19
  • 5
  • 27
• ĐỒ ÁN NHẬP MÔN PHÂN TÍCH ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
  • 31
  • 3
  • 56
• 3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN pptx
  • 7
  • 711
  • 6
• Ký thiệu " O lớn " và khái niệm độ phức tạp của thuật toán ppsx
  • 3
  • 1
  • 5
• Độ phức tạp của thuật toán pot
  • 4
  • 510
  • 1
• Độ phức tạp của thuật toán pptx
  • 17
  • 499
  • 1
• Nhập môn phân tích thông tin có bảo mật
  • 324
  • 1
  • 4

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(575.5 KB - 31 trang) - ĐỒ ÁN NHẬP MÔN PHÂN TÍCH ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Tải bản đầy đủ ngay ×