TAILIEUCHUNG - Bài giảng Phân tích thiết kế giải thuật: Chương 2 - Trịnh Huy Hoàng

Bài giảng Phân tích thiết kế giải thuật: Chương 2 do Trịnh Huy Hoàng biên soạn sau đây sẽ bổ sung thêm cho các bạn những kiến thức về phân tích các thuật toán sắp xếp và tìm kiếm. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này. | Chương 2: Phân tích các thuật toán sắp xếp và tìm kiếm Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM Mục đích Áp dụng kí pháp O lớn để phân tích đánh giá các phương pháp sắp xếp: Sắp xếp bằng phương pháp chọn (selection sort) Sắp xếp bằng phương pháp chèn (insertion sort) Sắp xếp bằng phương pháp đổi chỗ (interchange sort) Sắp xếp bằng phương pháp nổi bọt (bubble sort) Sắp xếp bằng phương pháp Shell (Shell Sort) Sắp xếp bằng phương pháp trộn (merge sort) Sắp xếp bằng phương pháp vun đống (heap sort) Sắp xếp nhanh (quick sort) Sắp xếp bằng phương pháp thẻ (bucket sort) Sắp xếp bằng phương pháp cơ số (radix sort) Sắp xếp bằng phương pháp chọn Ý tưởng: Tìm phần tử nhỏ nhất đưa về đầu dãy hiện tại Tiếp tục thực hiện phần còn lại của dãy Thuật toán: Algorithm selectSort(A) Input: Một mảng n phần tử số A Output: Mảng A đã được sắp xếp tăng dần. For i ← 1 to n-1 do min ← i For j ← i+1 to n do if A[j] Phân tích SX bằng pp chọn Vòng lặp ngoài (biến i) được thi hành n-1 lần: O(n) Tăng i: n-1 lần Kiểm tra i: n lần Gán i vào min: n-1 lần Đổi chỗ: tối đa n-1 lần Với mỗi giá trị của i, vòng lặp trong (biến j) được thi hành n-1-i lần tổng cộng (n-1) + (n-2) + + 1 = (n-1)n/2 lần: O(n2) So sánh: (n-1)n/2 lần Gán: tối đa (n-1)n/2 lần Phân tích SX bằng pp chọn (tt) Thời gian thực thi: T(n) = O(n) + O(n2) = O(n2+n) = O(n2) Sắp xếp bằng phương pháp chèn Ý tưởng: Chèn từng phần tử một vào dãy đã được sắp xếp đến bước hiện tại, vào đúng vị trí của nó để bảo đảm sau khi chèn dãy vẫn có thứ tự Thuật toán: Algorithm insertSort(A) Input: Một mảng n phần tử số A Output: Mảng A đã được sắp xếp tăng dần. For i ← 2 to n do temp ← A[i] j ← i - 1 while temp 0 do A[j+1] ← A[j] j ← j - 1 A[j+1] ← temp Return array A Phân tích thuật toán SX bằng pp chèn Vòng lặp for (biến i) được thực hiện n-1 lần Tăng i: n-1 lần So sánh i với n: n lần Gán giá trị vào các biến .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.