Tài liệu, ebook Công Nghệ Thông Tin

Gọi T(n) là thời gian để tính Ckn Thì thời gian để tính Cmn-1 là T(n-1) Khi n=1 thì k=0 hoac k=1 => CT trả về giá trị 1, tốn O(1) = C1 Khi n>1, trong trường hợp xấu nhất, CT phải làm các việc: Tính Ckn-1 và Ck-1n-1, tốn 2T(n-1). Phép cộng, trả kq, tốn C2 Ta có pt: T(1)=C1 và T(n)=2T(n-1) +C2

56 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1804 | Lượt tải: 0

Tập tin B-cây: Thêm mẩu tin mới Tìm r. Việc tìm kiếm này sẽ dẫn đến nút lá L. Nếu tìm thấy thì thông báo “Mẩu tin đã tồn tại”, ngược lại thì L là nút lá mà ta có thể xen r vào trong đó. Nếu khối L này còn chỗ cho r thì ta thêm r vào sao cho đúng thứ tự của nó trong khối L và giải thuật kết thúc. Nếu L không còn chỗ thì cấp phát một khối mới ...

53 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1461 | Lượt tải: 0

Kỹ thuật nhánh cận: BTcái ba lô Trong các nút con, ta sẽ ưu tiên phân nhánh cho nút con nào có cận trên lớn hơn trước. Các con của nút này tương ứng với các khả năng chọn đồ vật có đơn giá lớn tiếp theo. Với mỗi nút ta lại phải xác định lại các thông số TGT, W, CT theo công thức đã nói trong bước 2. Lặp lại bước 3 với chú ý: đối với những nút có ...

87 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1705 | Lượt tải: 1

Phân tích HeapSort Hàm PushDown lấy O(logn). Trong HeapSort, Vòng lặp /*1*/-/*2*/ lặp (n-2)/2+1 lần mà mỗi lần lấy O(logn) nên thời gian thực hiện /*1*/-/*2*/ là O(n logn). Vòng lặp /*3*/-/*5*/ lặp n-2 lần, mỗi lần lấy O(logn) nên thời gian thực hiện của /*3*/-/*5*/ là O(n logn). Thời gian thực hiện HeapSort là O(nlogn).

64 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1319 | Lượt tải: 0

2. Bảng băm đóng  Bảng băm mở: chỉ dùng để lưu trữ các liên kết trỏ đến các thành phần dữ liệu có khóa tương ứng.  Bảng băm đóng: bảng băm mà mỗi thành phần của nó lưu trữ chính các thành phần dữ liệu. Các phƣơng pháp xử lý: a) Băm lại tuyến tính Hi (x) = (H(x)+i) mod m – Nhận xét: Các giá trị hàm băm xếp thành từng đoạn con, nên việc tì...

6 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1532 | Lượt tải: 0

Nhận xét – Tất cả các thao tác tìm kiếm, thêm, xoá đều có độ phức tạp trung bình O(h), với h là chiều cao của cây – Trong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự. – Trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 danh sách liên ...

6 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1423 | Lượt tải: 0

Ứng dụng Queue Tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng, và quay lui vét cạn, Tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, Tổ chức bộ đệm bàn phím, ví dụ : Nhấn phím => Bộ đệm => CPU xử lý

34 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1578 | Lượt tải: 1

Cấu trúc dữ liệu cho bài toán Cấu trúc dữ liệu của một sinh viên typedef struct { char tên[40]; char Maso[40]; float ĐTB; }SV Cấu trúc dữ liệu của 1 nút trong xâu typedef struct tagNode { SV Info; struct tagNode *pNext; }Node;

38 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 2500 | Lượt tải: 0

Mối liên hệ giữa các phần tử được thể hiện ngầm: xi : phần tử thứ i trong ds xi , xi+1 là kế cận trong danh sách Phải lưu trữ liên tiếp các phần tử trong bộ nhớ công thức xác định địa chỉ phần tử thứ i: address(i) = address(1) + (i-1)*sizeof(T) Ưu điểm : Truy xuất trực tiếp, nhanh chóng Nhược điểm: Sử dụng bộ nhớ kém hiệu quả Kích thướ...

19 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1452 | Lượt tải: 0

Bài Tập  Nhập một dãy số nguyên n phần tử.  Sắp xếp lại dãy sao cho:  số nguyên dương đầu ở đầu dãy và theo thứ tự giảm.  số nguyên âm tăng ở cuối dãy và theo thứ tự tăng.  số 0 ở giữa.  Lưu ý: Không dùng đổi chỗ trực tiếp

18 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1408 | Lượt tải: 0