Tìm hiểu phương pháp chủ và các định lý chủ

Phương pháp chủ cung cấp một phương pháp kiểu “sách nấu ăn” để giải các phép truy toán có dạngT(rì) – aT(rƯb)+ /(«), (45)ở đó a> 1 và b> 1 là các hằng và /(n) là một hàm dương theo tiệm cạn. Phương pháp chủ yêu cầu phải nhó ba trường hợp, nhưng sau đó nghiệm của nhiều phép truy toán có thể được xác …

Tiểu tiết kĩ thuật để suy đoán tốt

Đáng tiếc, không có một cách chung nào để suy đoán các nghiệm đúng đắn cho các phép truy toán. Việc suy đoán một nghiệm đòi hỏi sự kinh nghiệm và, đôi lúc, cả óc sáng tạo. Tuy nhiên, may thay, có vài phép phỏng đoán có thể giúp ta trở thành người suy đoán tốt.Nếu một phép truy toán tương tự như đã …

Giải thích và đưa ví dụ về định lý chủ

Phương pháp chủ cung cấp một phương pháp kiểu “sách nấu ăn” để giải các phép truy toán có dạngT(rì) – aT(rƯb)+ /(«), (45)ở đó a> 1 và b> 1 là các hằng và /(n) là một hàm dương theo tiệm cạn. Phương pháp chủ yêu cầu phải nhó ba trường hợp, nhưng sau đó nghiệm của nhiều phép truy toán có thể được xác …

Phương pháp lặp một phép truy toán đặc biệt

Phương pháp lặp một phép truy toán không yêu cầu ta suy đoán câu ưả lời, nhưng nó cổ thể yêu cầu nhiều đại sô”hơn phương pháp thay thế. Ý tưởng đó là mở rộng (lặp lại) phép ưuy toán và diễn tá nó dưới dạng một phép lâ”y tổng các số hạng chỉ lệ thuộc vào n và các điều kiện ban đầu. Như …

Phương pháp thay thê

Trong thực tế, ta không đểý đến một số chi tiết kỷ thuật nhất định khi phát biểu và giải quyết các phép truy toán. Một ví dụ tốt về một chi tiết thường được xem nhẹ đó là giả thiết về các đối số số nguyên cho các hàm. Thông thường, thời gian thực hiện T(n) của một thuật toán chỉ được định nghĩa …

Các phép truy toán của thuật toán cơ bản

Khi một thuật toán chứa một lệnh gọi đệ quy lên chinh nó, ta có thể dùng phép truy toán để mô tá thời gian thực hiện của nó. Một phép truy toán là một phương trình hoặc bất đẳng thức mô tả một hàm theo dạng giá trị của nó dựa trên các nhập liệu nhỏ hơn. Ví dụ, ta đã thấy trong Chương …

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 …