Tách các phép lấy tổng

Một cách để có các cận dựa trên một phép lấy tổng khác đó là diễn tả chuỗi dưới dạng tổng của hai hay nhiều chuỗi bằng cách phân hoạch miền của chỉ số rồi định cận từng chuỗi kết quả. Ví dụ, giả sử ta gắng tìm một cận dưới dựa trên chuỗi câ”p sô” cộng ỵ.L\k, đã được chứng tỏ là có …

Các tính chất và công thức lây tổng

Khi một thuật toán chứa cấu trúc điều khiển lặp như vòng lặp while hoặc for, thời gian thực hiện của nó có thể được diễn tả dưới dạng tổng của các lần bỏ ra cho mỗi đợt thi hành của thân vòng lặp* Ví dụ, trong Đoạn 1.2 ta thấy lần lặp lại thứjcủa tiến trình sắp xếp chèn chiếm một thời gian tỷ …

Hệ ký hỉệu Q trong thuật toán máy tính

Giống như hệ ký hiệu ocung cấp một cận trên tiệm cận trên một hàm, hệ ký hiệu Q cung cấp một cận dưới tiệm cận. Với một hàm đã cho g(n), bằng Q(g(/ĩ)) ta thể hiện tập hợp các hàm Q(g(rt)) = ỈẨn):ở đó tồn tại các hằng dương c và nữ sao cho 0 <cgịn) < fịn) với tất cản > n0\ . …

Sự Tăng trưởng của Các hàm

Hệ ký hiệu tiệm cận Các ký hiệu mà ta dùng để mô tả thời gian thực hiện tiệm cận của một thuật toán được định nghĩa theo dạng các hàm có các lĩnh vực là tập hựp các số tựnhiên N = {0, 1, 2,…}. Các ký hiệu như vậy tỏ ra tiện dụng khi mô tả hàm thời gian thực hiện ca xấu …

Các bài toán về thuật toán chia để trị

1.4- 1Giả sử ta đang so sánh các cách thực thi phương pháp sắp xếp chènvà sắp xếp trộn trên cùng một máy. Với các đdu vào có kích cỡn> tiến trình sắp xếp chèn chạy trong 8n2 bước, trong khi tiến trình sắp xếp trộn chạy trong 64nìg n bước. Với các giá trịn nào, phương pháp sắp xếp chèn sẽ đánh bại phương …

Phân tích các thuật toán chia để trị

Khi một thuật toán chứa một lệnh gọi đệ quy lên chính nó, thời gian thực hiện của nó thường được mô tả bởi một phương trình truy toán hoặc phép truy toán, mô tá thời gian thực hiện chung trên một bài toán có kích cỡn theo dạng thời gian thực hiện trên các đầu vào nhỏ hơn. Như vậy, có thể dùng các …

Cách thiết kế các thuật toán

Có nhiều cách để thiết kế các thuật toán. Phương pháp sắp xếp chèn sử dụng cách tiếp cận gia^: khi sáp xếp mảng con A, ta chèn một thành phần A vào đúng chỗ của nó, cho ra mảng con đã sắp xếp A. Trong đoạn này, ta xem xét một cách tiếp cận thiết kế khác, có tên “chia để trị” . Ta …

Phân tích trường hợp xấu nhất trong thuật toán sắp xếp chèn

Trong kỹ thuật phân tích sắp xếp chèn trên đây, ta đã xem xét cả ca tốt nhất, ỏ đó mảng đầu vào đã được sắp xếp sẩn, lẫn trường hợp xấu nhất, ở đó mảng đầu vào được sắp xếp đảo ngược. Tuy nhiên, với phần còn lại của cuốn sách, ta thường tập trung vào việc chỉ tìm thời gian thực hiện trường …

Phân tích các thuật toán cơ bản

Phân tích một thuật toán thường hàm ý tiên liệu các tài nguyên mà thuật toán yêu cầu. Thỉnh thoảng, các tài nguyên như bộ nhớ, băng thông, hoặc các cổng logic là những yếu tô” được quan tâm hàng đầu, song đa phần chính thời gian tính toán mới là yếu tố mà ta cần đo lường. Nói chung, nhờ phân tích vài thuật …

Thuật toán sắp xếp chèn là gì ?

Trước tiên, ta tìm hiểu phương pháp sắp xếp chèn,đây là một thuật toán hiệu quả để sắp xếp các thành phần có số lượng nhỏ. Kỹ thuật sắp xếp chèn làm việc giống như cách thức mà nhiều người xếp một tay bài tây hay bài rumi. Ta bất đầu bằng một tay trái trắng với các lá bài tung sấp trên bàn. Sau …