Tài liệu, ebook Cơ Sở Dữ Liệu

G = (V, E) là đồ thị định hướng không chu trình Sắp xếp các đỉnh đồ thị thành một danh sách Sao cho nếu có cung (u,v) thì u cần đứng trước v trong danh sách đó Sắp xếp topo dựa trên DFS Thực hiện DFS trên đồ thị Khi kết thúc quá trình DFS trên một đỉnh u thì thêm u vào cuối danh sách Kết thúc DFS trên toàn đồ thị, đảo ngược danh sách, ...

22 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 687 | Lượt tải: 0

Xóa một cạnh bất kỳ (u, v) ∈ T. Thì, cây T được chia thành 2 cây con T_1 và T_2 Định lý. Cây con T_1 là cây bao trùm nhỏ nhất của G_1=(V_1, E_1) là đồ thị con của G bao gồm các đỉnh của T_1 V_1 = đỉnh của T_1 E_1= {(x,y)∈E:x,y ∈ V_1 } Tương tự với T_2 Thuật Toán Prim U: tập các đỉnh kề các cạnh trong tập cạnh T Ban đầu tập U chứa một đ...

25 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 712 | Lượt tải: 0

Kiểm tra tất cả các dãy con của x[1 . . m] xem có phải dãy con của y[1 . . n] không Phân tích Kiểm tra = 0 (n) cho mỗi dãy con. Có 2^m dãy con của x. Thời gian chạy xấu nhất = 0 (n2m), thời gian hàm mũ.

22 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 664 | Lượt tải: 0

Giả thiết dữ liệu trong khoảng [0, 1) Tạo ngẫu nhiên Phân bố đồng đều Độc lập với nhau Ý tưởng Chia khoảng dữ liệu thành phần bằng nhau Phân bố dữ liệu vào các giỏ Sắp xếp từng giỏ Liệt kê phần tử trong giỏ Sắp Xếp Giỏ Trường hợp tốt nhất, mỗi dữ liệu được phân vào một giỏ Trường hợp khác, sắp xếp từng giỏ sử dụng sắp xếp chè...

26 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 706 | Lượt tải: 0

Tuyến tính Ưu điểm: xét tất cả các vị trí trong mảng Phép chèn luôn thực hiện được, trừ khi mảng đầy Nhược điểm: Dữ liệu tập trung thành các đoạn Tìm kiếm tuần tự trong từng đoạn Bình phương Ưu điểm: tránh nhược điểm thăm dò tuyến tính Nhược điểm: không xét tất cả các vị trí trong mảng Phép chèn có thể không thực hiện được Băm k...

19 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 656 | Lượt tải: 0

Các thao tác chèn và xóa có thể làm thay đổi tính chất của cây Do chính các thao tác này Đổi màu các nút Cấu trúc lại các kết nối nút Phép xoay: đảm bảo thứ tự trong của khóa Phép thực hiện trong thời gian 0 (1) Georgy Adelson-Velsky & Evgenil Landis đề xuất năm 1962 Độ cao 2 cây của của một nút khác nhau nhiều nhất 1 Thời gian 0(log n) ...

22 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 719 | Lượt tải: 0

Chèn liên tục vào MinHeap, nhưng không khôi phục tính chất thứ tự bộ phận.Khôi phục tính chất thứ tự bộ phận (sử dụng downheap) bắt đầu từ đỉnh chính giữa Sắp Xếp Cây Thứ Tự Bộ Phận – So Sánh Giống sắp xếp gộp (merge sort) Độ phức tạp 0 (n logn) Giống sắp xếp chèn (insertion sort) In-place algortihm

35 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 786 | Lượt tải: 0

Phân hoạch dựa trên phần tử ngẫu nhiên: Thời gian chạy không phụ thuộc vào dữ liệu đầu vào. Không cần giả thiết về phân phối của dữ liệu đầu vào. Không dữ liệu nào tạo nên trường hợp xấu nhất. Trường hợp xấu nhất chỉ do hàm sinh số ngẫu nhiên. Giả thiết khi phân tích thời gian chạy Mảng bao gồm các phần tử khác nhau Mảng có các phần tử g...

20 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 675 | Lượt tải: 0

T(n) = 7T(n/2) + Ө (n^2) n^log_b⁡a =n^log_2⁡7 = n^2.81 => T(n) ∈ Ө (n^log7) log 7 = 2.81 trông không nhỏ hơn 3 là mấy. Tuy nhiên, nên nhớ sự khác biệt là số mũ. Do đó thời gian chạy sẽ bị ảnh hưởng rất nhiều. Trên thực thế, thuật toán Strassen’s tốt hơn thuật toán nhân ma trận thông thường với n ≥ 32

21 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 1058 | Lượt tải: 0

T(n) = 4T(n/2) + n^2 log⁡n a = 4, b = 2 => n^log_b⁡a =n^2 f(n) = n^2 logn Không áp dụng được Định lý Tổng quát af (n/b) ≤ cf (n) với c < 1 4 ((〖n/2)〗^2 log⁡〖n/2〗) ≤ cn^2 logn với c < 1 n^2 logn - n^2 ≤ cn^2 logn với c < 1 (1-c) logn ≤ 1 với c < 1

28 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 667 | Lượt tải: 0