TAILIEUCHUNG - Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p6

Tham khảo tài liệu 'giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình poisson với tham số p6', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Thuật toán Prim dựa trên những định lý sau đây Định lý . Một cây là một MST nếu và chỉ nếu cây đó chứa cạnh ngắn nhất trong mọi cutset chia các nút thành hai thành phần. Để thực hiện thuật toán Prim cần phải theo dõi khoảng cách từ mỗi nút không thuộc cây tới cây và cập nhật khoảng cách đó mỗi khi có một nút được thêm vào cây. Việc đó được thực hiện dễ dàng đơn giản chỉ là duy trì một dãy d_tree có các thông tin về khoảng cách đã nói ở trên. Quá trình đó tuân theo array n - Prim n root dist dcl dist n n pred n d_tree n in tree n index - FindMin d_min - INFINITY for each i n if in_tree j and d_tree i d min i min - i d min - d tree i return i min void -Scan i for each j n if in_tree j and d_tree j dist i j d_tree j - dist i j pred j -i d_tree - INFINITY pred - -1 in_tree - FALSE d_tree root -0 in tree -0 while in tree n i - FindMin in_tree i - TRUE Scan i _in_tree _in_tree 1 return pred FindMin trả về một nút không thuộc cây và gần cây nhất. Scan cập nhật khoảng cách tới cây đối với các nút không thuộc cây. 57 Có thể thấy rằng độ phức tạp của thuật toán này là O n2 cả hai hàm FindMin và Scan có độ phức tạp là O n và mỗi hàm được thực hiện n lần. So sánh với thuật toán Kruskal ta thấy rằng độ phức tạp của thuật toán Prim tăng nhanh hơn so với độ phức tạp của thuật toán Kruskal nếu m số lượng các cạnh bằng O n2 còn nếu m có cùng bậc với n thì độ phức tạp của thuật toán Kruskal tăng nhanh hơn. Có thể tăng tốc thuật toán Prim trong trường hợp graph là một graph mỏng bằng cách chỉ quan tâm đến các nút láng giềng của nút i vừa được thêm vào cây. Nếu sẵn có các thông tin kề liền vòng lặp for trong Scan có thể trở thành. for each j n_adj_list i Độ phức tạp của Scan trở thành O d với d là bậc của nút i. Chính vì thế độ phức tạp tổng cộng của Scan giảm từ O n2 xuống O m . Thiết lập một tập kề liền cho toàn bộ một graph là một phép toán có độ phức tạp bằng O m index nn list - SetAdj n m ends dcl ends m 2 n adj list n list for node 1 to n n adj list node - 0 for edge 1 to m .

• Toán học
• giáo trình đại số
• giáo trình lượng giác
• phương pháp học toán
• mẹo học toán cao cấp
• kỹ năng học toán
• Giáo án đại số 12
• tài liệu giảng đại số 12
• giáo trình đại số 12
• tài liệu đại số 12
• cẩm nang giảng dạy đại số 12
• Giáo án Đại Số 10
• tài liệu giảng dạy Đại Số 10
• giáo trình Đại Số 10
• tài liệu Đại Số 10
• cẩm nang giảng dạy Đại Số 10
• Thông tư số 07 2015 TT BGDĐT
• Giáo dục đại học
• Trình độ đào tạo giáo dục đại học
• Quy trình xây dựng trình độ đại học
• Quy trình xây dựng trình độ thạc sĩ
• Quy trình xây dựng trình độ tiến sĩ
• Giáo án Đại Số 8
• tài liệu giảng dạy Đại Số 8
• giáo trình Đại Số 8
• tài liệu Đại Số 8
• cẩm nang giảng dạy Đại Số 8