ĐỀ TÀI: CÂy bao trùm nhỏ nhất học viên thực hiệN
tải về 0.76 Mb.
|
ATHTTT DDOS
- Điều hướng trang này:
- Randomizepartition
| Randomize Quicksort (A,p,r)
1. If p < r 2. Q = Randomizepartition (A, p , r) 3. Randomizequicksort (A, p, q – 1) 4. Randomizequicksort (A, q + 1, p) Randomizepartition (A, p, r) -> O(nlogn) 1. i = Random (p, r) 2. swap A[r] with A[i] 3. Return partition (A, p, r) - Độ phức tạp thuật toán: Trong quicksort trường hợp xấu nhất, mỗi bước ta đều chọn phải phần tử pivot A[p] mà hai phần có độ dài lệch nhau quá lớn thì thời gian của Quicksort sẽ là O(n2). Để tránh trường hợp xấu nhất này ta sẽ chọn A[p] ngẫu nhiên. Thuật toán có độ phức tạp : - Xác suất để phần tử được chọn ngẫu nhiên là trục trung tâm là 1 / n): * Thời gian chay của Randomizepartition: - Thời gian chạy của quicksort chủ yếu phụ thuộc vào số lượng so sánh được thực hiện trong tất cả các lệnh gọi đến RandomizedPartition. Gọi X là biến ngẫu nhiên đếm số lượng so sánh trong tất cả các lệnh gọi đến RandomizedPartition. - Gọi zi là phần tử nhỏ nhất thứ i của A [1..n]. - Do đó A [1..n] được sắp xếp là [z1, z2, ..., zn]. - Gọi Zij = {zi, ..., zj} biểu thị tập hợp các phần tử giữa zi và zj, - Xij = I {zi, zj}. Do đó, Xij là một biến ngẫu nhiên chỉ báo cho trường hợp phần tử nhỏ nhất thứ i v thứ j của A được so sánh trong một lần thực hiện quicksort. Ta có: E[X]= Mà Pij = P[phần tử j duoc chọn làm phần tử trục] + P[phần tử i được chọn làm phần tử trục] = 1/(j-i+1) + 1/(j-i+1) = 2/j-i+1. E[X] = = = O (nlogn) Thời gian chạy dự kiến của Randomized-QuickSort là O (n log n). 3.2.2. Thuật toán Klein, Karger và Tarjan ( KKT Algorithm) Thuật toán KKT là một thuật toán thời gian tuyến tính ngẫu nhiên để tìm một cây bao trùm tối thiểu trong một đồ thị liên thông với các cạnh có trọng số. Thuật toán sử dụng lấy mẫu ngẫu nhiên kết hợp với thuật toán thời gian tuyến tính để tìm cây bao trùm tối thiểu, phép toán duy nhất được sử dụng là phép so sánh nhị phân. Tổng quan về thuật toán có 5 bước như sau, Cho đồ thị có trọng số G(V,E) : Random_MST(G) 1. Chạy hai bước của thuật toán Boruvka để giảm các đỉnh theo hệ số 4. Cho Đặt biểu đồ thu được là G0 và tập các cạnh được quy ước là F0 2. Với mỗi cạnh e trong G, thêm e vào đồ thị con G1 với xác suất p. Chạy Random _MST(G1) và thu được MST của nó là F1. 3. Với mỗi cạnh e trong G, nếu thêm e vào F1 làm cho e trở thành cạnh nặng nhất trong chu kỳ thì loại bỏ e khỏi G. Cho đồ thị còn lại là G2. 4. Chạy Random MST(G2) và thu được MST của nó là F2. 5. Trả về F2 F0 Gọi F là một rừng của đồ thị G. Nếu một cạnh (u ; v) là F-heavy trong đồ thị G thì nó không thể là một phần của cây bào trùm tối thiểu G. Điều này lại là không đúng. Một cạnh (u; v) là F-heavy nếu thêm nó vào F sẽ tạo ra một chu trình và cạnh (u; v) > cạnh (u,v)f là cạnh nặng nhất trong chu kỳ đó. Ngược lại, cạnh (u ; v) là F-light. Ta có định nghĩa sau : Gọi G là đồ thị có n đỉnh, và gọi G0 là đồ thị con thu được bằng cách gộp từng cạnh độc lập với xác suất p, và gọi F là rừng bao trùm nhỏ nhất của G. Số cạnh F-light dự kiến trong G nhiều nhất là n = p. Mã giả thuật toán: tải về 0.76 Mb. Chia sẻ với bạn bè của bạn:
|