Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuố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 . | 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] < A[min] then min ← j swap(A, i, min) Return array A .
