TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

c. Phân tích thuật toán: - Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X: Số phép gán: Gmin = 1 Số phép so sánh: Smin = 2 + 1 = 3 - Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X: Số phép gán: Gmax = 1 Số phép so sánh: Smax = 2N+1 - Trung bình: Số phép gán: Gavg = 1 Số phép so sánh: Savg ...

29 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2136 | Lượt tải: 0

Bài toán: Nhân 2 ma trận vuông cùng cấp nxn C=A x B PP vẫn làm O(n3) Tiếp cận theo chia để trị: xem như nhân 2 x 2 2 mà mỗi phần tử của nó là một ma trận n/2 x n/2 để xác định được ma trận C ta phải mất 8 phép nhân ma trận n/2 x n/2, và 4 phép cộng

36 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2203 | Lượt tải: 1

Ngăn xếp đầy không liên quan đến cấu trúc dữ liệu (về mặt lý thuyết là kô có giới hạn) Bd bằng mảng → kô chính xác

34 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2681 | Lượt tải: 0

Nguyên tắc (playing card): 1 khóa luôn được sắp, xét thêm s2, so sánh với s1 để xác định chỗ để chèn s2 vào. Tương tự như đối với s3, s4, s5,.v.v. cuối cùng sau khi xét xong sn ta được dãy được sắp. Tìm vị trí để chèn phần tử Dịch chuyển các phần tử khác

52 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2103 | Lượt tải: 0

Một cây M - đường T là tập hữu hạn khóa hoặc là rỗng hoặc là tập của n cây con M-đường T0, T1, ., Tn-1 và n-1 khóa k1, k2, ., kn-1, với 2  n  M sao cho các khóa và các nút thỏa mãn tính chất sau: Các khóa trên mỗi nút khác nhau và được sắp: ki < ki+1 với 1  i  n-1 Tất cả các khóa trên cây con Ti-1 đều nhỏ hơn ki: kTi-1: k < ki với 1  i ...

27 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 1897 | Lượt tải: 0

While p<> nil do Begin Attach(p^.Coef, p^.Exp, d); p:=p^.Link; End While q<> nil do Begin Attach(q^.Coef, q^.Exp, d); q:=q^.Link; End d^.link:=nil; T:=c; c:=c^.link; dispose(T); End {of procedure}

8 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 1891 | Lượt tải: 0

Điều kiện để một danh sách liên kết rỗng là head = null Danh sách liên kết chỉ đầy khi không còn không gian nhớ để cấp phát cho các thành phần mới của danh sách. giả thiết điều này không xảy ra -> insert luôn luôn thực hiện được

31 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2288 | Lượt tải: 0

b) Xoá một phần tử của mảng void Delete_Arr(*a:m, int p, int t); //p: vị trí của phần tử cần xoá; t: tổng số phần tử hiện có trong mảng { int i; for (i=p; i<=t-1; i++) a[i]=a[i+1]; t=t-1; }

9 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 1790 | Lượt tải: 0

Một thủ tục đệ qui gồm có hai phần chính Phần cố định (neo): gía trị khởi đầu cho hàm, thủ tục đệ qui. Phần hạ bậc (phần đệ qui): Tác động của hàm đệ qui được thực hiện thông qua tác động hay giá trị đã được định nghĩa trước. Phân tích giải thuật đệ qui tính giai thừa: f(3)->f(2)->f(1)->f(0)->1 -> như vậy để tính 3! Hàm f được gọi 4 lần. Ph...

15 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2882 | Lượt tải: 0

cài đặt hàng bởi mảng với hai chỉ số front, rear có điểm yếu lớn: Nếu phép loại bỏ không thường xuyên làm cho hàng rỗng, chỉ số front và rear sẽ tăng liên tục, nhanh chóng vượt quá cỡ của mảng. Hàng sẽ trở thành đầy, mặc dầu các vị trí trống trong mảng có thể vẫn còn nhiều khắc phục bằng cách sau: chỉ sử dụng một chỉ số rear để chỉ cuối hàng, ph...

13 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2214 | Lượt tải: 1