Tài nguyên

Chúc mừng năm mới 2013

Liên kết Blog

Website Nam Đàn I

Thông tin

Ảnh ngẫu nhiên

Mauchuvietbangchuhoadung.png Thay_co_giao.jpg 14_viet_chu_q_g.swf 13_chu_d_dtd.swf 11luyen_chu_o.swf 0.Cfe_muoi!.swf Thiep_Xuan_cua_Ong_Do.swf Bai_ca_tet_cho_em.swf Noel5.swf Lich_phat_tai1.swf On_thay_112011.swf On_thay_112011.swf Teachersday__776.swf 28__Tao_va_hieu_chinh_Word_Art.swf 27__Thiet_lap_Numbering.swf 26__Thiet_lap_ki_tu_Bullist_.swf 25__Thiet_lap_khoang_cach_dong.swf 22__Them_noi_dung_VB.swf 20__Mau_nen_Texture_hoac_hinh_anh.swf

Hỗ trợ trực tuyến

  • (Trần Trung)

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Thành viên trực tuyến

    0 khách và 0 thành viên

    Sắp xếp dữ liệu

    Hour and Date

    Cảnh đẹp Việt Nam

    Khách tới vui vẻ nhe chú!

    Chào mừng quý vị đến với Trang riêng Trần Trung!.

    Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
    Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.

    Phân tích một số thuật toán.

    Nhấn vào đây để tải về
    Hiển thị toàn màn hình
    Báo tài liệu có sai sót
    Nhắn tin cho tác giả
    (Tài liệu chưa được thẩm định)
    Nguồn: uit.edu.vn
    Người gửi: Nguyễn Tấn Thành
    Ngày gửi: 20h:12' 21-03-2011
    Dung lượng: 66.7 KB
    Số lượt tải: 51
    Số lượt thích: 0 người
    PHÂN TÍCH MỘT SỐ THUẬT TOÁN


    Thuật toán tìm Max
    Thuật toán M: Tìm giá trị lớn nhất trong dãy x[1], x[2], …, x[N]
    Begin
    j:=1; m := x[1];
    for i:=2 to N do
    if x[i] > m then
    m := x[i];
    j := i;
    end if
    end do
    End

    Có thể chứng minh thuật toán M là đúng bằng nguyên lý qui nạp.
    Nếu gọi ( là thời gian thực hiện một phép so sánh và ( là thời gian thực hiện một phép gán thì thời gian thực hiện thuật toán M là:
    T= 2 ( + (N-1) ( + 2 AN (
    Trong đó AN là số lần mà điều kiện x[i] > m được thỏa trong vòng lặp for. Nói cách khác AN số những i thỏa điều kiện sau đây:
    x[i] = Max {x[k], 1 ( k ( i}
    Có thể thấy rằng 0 ( AN ( N-1. Từ đó ta suy ra độ phức tạp (trung bình) của thuật toán M là O(ln(n)) vì dựa trên kỹ thuật tính toán dùng hàm sinh ta có thể chứng minh được rằng
    mean(AN) = Hn – 1 = O( ln(n) )
    và độ lệch là
    ( = 

    Chứng minh:

    Ta tính giá trị trung bình của AN dựa trên 2 giả thiết sau:
    dãy các x[i] đôi một khác nhau, và
    mọi phép hoán vị đều có thể xảy ra với xác suất như nhau (là 1/N!).
    Ký hiệu pNk là xác suất để AN = k.
    Ta có:
    pNk = (số hoán vị mà AN = k) / N!
    Có thể kiểm tra được công thức sau đây (bài tập):
    pNk = .pN-1,k-1 + .pN-1,k
    Xét hàm sinh
    
    Ta có thể kiểm tra thấy rằng:
    
    Suy ra
    
    Do đa thức  là hàm sinh của dãy {, } nên
    Ave() = .
    Từ đó
    Ave() =  = Hn-1.

    Số nghịch thế của một phép hon vị
    Định nghĩa:
    Cho ( là một hoán vị của n phần tử 1, 2, …, n. Một nghịch thế
    là một cặp (((i),((j)) thỏa
    ((i) > ((j) và i < j.
    Với j = 1, 2, …, n đặt
    bj = số các nghịch thế có thành phần thứ hai là j.
    Bảng b1, b2, …, bn được gọi là bảng nghịch thế của hoán vị (.
    Số các nghịch thế của ( là:
    I(() = 

    Ví dụ: Giả sử một hoán vị ( viết dưới dạng dòng như sau
    (((1) ((2) … ((n)) = (5 9 1 8 2 6 4 7 3)
    ( bảng nghịch thế là (2 3 6 4 0 2 2 1 0).

    Định lý:
    Có một tương ứng 1-1 giữa tập hợp các hoán vị n phần tử và
    các bảng nghịch thế.

    Tính chất:
    Đặt
    In(k) = số các hoán vị có k nghịch thế
    và qui ước In(k) = 0 nếu k < 0 hay k > .
    Ta có các tính chất:
    In(0) = 0
    In(1) = n-1
    In = In(k)
    In(k) = In-1(k) + In-1(k-1) + . . . + In-1(k-n+1)

    Số nghịch thế trung bình:
    Xét hàm sinh Gn(z) của phân bố xác suất .
    Do tính chất của In(k) ta có:
    Gn(z) = (1 + z + . . . + zn-1) Gn-1(z)
    ( Gn(z) = Gn-1(z)
    ( Gn(z) = 

    hk(z) =  = (1 + z + . . . + zk-1)
    là hàm sinh của phân bố xác suất  nên có thể tính toán được
    mean(hk) = 
    Var(hk) = 
    Suy ra:
    Mean(Gn) =  = 
    Var(Gn) =  = 

    Tóm lại ta có định lý sau đây:

    Định lý: Số nghịch thế trúng bình là  = O(n2) với độ lệch ( = O().

    Sắp xếp bằng cách đếm
    Xét bài toán sắp xếp
     
    Gửi ý kiến

    ↓ CHÚ Ý: Bài giảng này được nén lại dưới dạng RAR và có thể chứa nhiều file. Hệ thống chỉ hiển thị 1 file trong số đó, đề nghị các thầy cô KIỂM TRA KỸ TRƯỚC KHI NHẬN XÉT  ↓


    Cho Rùa tí mồi nhé!