Nội dung của tập bài giảng Thiết kế và đánh giá thuật toán trình bày các kỹ thuật thiết kế thuật toán thông dụng và cơ sở phân tích, đánh giá độ phức tạp của thuật toán. Tập bài giảng gồm 6 chương như sau: Chương 1 - Tổng quan về thiết kế và đánh giá thuật toán; Chương 2 - Kỹ thuật chia để trị; Chương 3 - Kỹ thuật tham lam; Chương 4 - Kỹ thuật quay lui; Chương 5 - Kỹ thuật nhánh và cận; Chương 6 - Kỹ thuật quy hoạch động. Mời các bạn cùng tham khảo.
Tổng quan về thiết kế và đánh giá thuật toán 1
Thuật toán 1
Thuật toán, khái niệm đã xuất hiện từ lâu, ban đầu được hiểu là các quy tắc thực hiện phép tính số học với số trong hệ thập phân Với sự phát triển của máy tính, thuật toán đã được mở rộng về nghĩa, và được định nghĩa chính xác thông qua máy Turing Trong bài viết này, chúng ta sẽ xem xét khái niệm thuật toán một cách trực quan.
Thuật toán (hay giải thuật, thuật giải) là một khái niệm cơ sở của tin học Mỗi bài toán trong thực tế bao gồm hai phần:
- Input: Các đại lượng cho trước (đại lượng vào)
- Output: Các đại lượng cần tìm (đại lượng ra)
Giải bài toán là quá trình xác định rõ ràng đầu ra (output) dựa trên đầu vào (input) thông qua các thao tác hiệu quả Đây là nội dung cốt lõi của lý thuyết tính toán Khi tiếp nhận một bài toán, mục tiêu là tìm ra một chuỗi hữu hạn các thao tác đơn giản được sắp xếp theo trình tự cụ thể, từ đó chuyển đổi đầu vào thành đầu ra mong muốn.
Thuật toán giải quyết một bài toán có thể được hiểu là một chuỗi hữu hạn các chỉ dẫn rõ ràng và chính xác, được sắp xếp theo một trình tự nhất định Sau một số lần thực hiện các chỉ dẫn này, thuật toán sẽ biến đổi input thành output một cách hiệu quả.
1.1.2 Các đặc trƣng cơ bản của thuật toán
Mỗi thuật toán có thể có một hoặc nhiều đại lượng vào mà ta thường gọi là dữ liệu vào
Sau khi hoàn thành thuật toán, tùy thuộc vào chức năng mà thuật toán thực hiện, chúng ta có thể thu được một số đại lượng gọi là dữ liệu đầu ra.
Tính xác định của thuật toán yêu cầu các thao tác phải rõ ràng và nhất quán ở mỗi bước, tránh sự nhập nhằng và tùy tiện Điều này có nghĩa là trong cùng một điều kiện, hai bộ xử lý (có thể là con người hoặc máy móc) cần thực hiện cùng một bước một cách đồng nhất.
Thuật toán phải dừng và cho kết quả sau một số hữu hạn bước thực hiện
Để đảm bảo tính hiệu quả, cần lựa chọn thuật toán tốt nhất trong số các thuật toán thực hiện cùng một chức năng Thuật toán tốt được hiểu là thuật toán có khả năng thực hiện nhanh chóng, tiết kiệm thời gian và sử dụng ít tài nguyên lưu trữ cho các kết quả trung gian.
Một thuật toán được coi là phổ dụng khi nó có khả năng giải quyết mọi bài toán trong một lớp bài toán nhất định, thay vì chỉ áp dụng cho một bài toán cụ thể.
Sự cần thiết của thiết kế và đánh giá thuât toán 2
Xây dựng một thuật toán hiệu quả là yếu tố then chốt trong việc giải quyết bài toán trên máy tính Để phát triển một thuật toán tốt, người lập trình cần hiểu rõ các kỹ thuật thiết kế, phân tích và đánh giá thuật toán, cũng như nắm vững các thuật toán cơ bản cho những loại bài toán điển hình.
Khi giải quyết một bài toán, có nhiều thuật toán khác nhau có thể được áp dụng, tuy nhiên, việc đánh giá và lựa chọn thuật toán tốt nhất là rất quan trọng Để thực hiện điều này, chúng ta thường dựa vào một số tiêu chí nhất định.
(3) Thuật toán thực hiện nhanh
Để kiểm tra tính đúng đắn của thuật toán, chúng ta có thể cài đặt và chạy thuật toán trên máy với một số bộ dữ liệu mẫu, sau đó so sánh kết quả thu được với kết quả đã biết Tuy nhiên, phương pháp này không đảm bảo tính chính xác, vì thuật toán có thể đúng với các bộ dữ liệu đã thử nhưng lại sai với một bộ dữ liệu khác Hơn nữa, phương pháp này chỉ phát hiện sai sót của thuật toán mà không chứng minh được tính đúng đắn của nó Để khẳng định tính đúng đắn của thuật toán, cần có sự chứng minh bằng toán học, điều này là không đơn giản và sẽ không được đề cập ở đây.
Khi viết một chương trình để sử dụng nhiều lần, hiệu quả thời gian thực hiện trở nên rất quan trọng, đặc biệt khi chương trình cần xử lý dữ liệu lớn Trong trường hợp này, yêu cầu tiết kiệm thời gian thực hiện sẽ được xem xét kỹ càng, vì chương trình sẽ được sử dụng thường xuyên Ngược lại, đối với những chương trình chỉ sử dụng một vài lần, việc có một giải thuật dễ viết và nhanh chóng đạt được kết quả sẽ được ưu tiên hơn.
Diễn tả thuật toán 3
Có nhiều cách diễn tả thuật toán Người ta thường diễn tả thuật toán bằng một trong các cách sau:
Thuật toán có thể trình bày dưới dạng ngôn ngữ tự nhiện theo trình tự các bước thực hiện trong thuật toán
2) Sơ đồ khối (Lưu đồ)
Sử dụng hình vẽ có qui ước để mô tả thuật toán là một phương pháp hiệu quả Lưu đồ cung cấp cái nhìn trực quan và tổng thể về quy trình của thuật toán, do đó nó thường được ưa chuộng trong việc minh họa các bước thực hiện.
Dùng cấu trúc lệnh, dữ liệu của một ngôn ngữ lập trình nào đó để mô tả
Thuật toán thường được trình bày dưới dạng văn bản bằng ngôn ngữ tự nhiên, dễ hiểu nhưng khó cài đặt Việc sử dụng ngôn ngữ lập trình để diễn tả có thể phức tạp và khó nắm bắt Thông thường, thuật toán được thể hiện bằng văn bản mà không bị ràng buộc nhiều vào cú pháp ngôn ngữ lập trình, nhưng vẫn tuân theo một số quy ước nhất định, được gọi là giả mã Cách trình bày thuật toán sẽ phụ thuộc vào ngôn ngữ lập trình mà người lập trình dự định sử dụng Trong tài liệu này, các thuật toán sẽ được trình bày dưới dạng giả mã theo ngôn ngữ lập trình C, kèm theo một số quy ước cơ bản của ngôn ngữ này.
- Bộ chữ cái: 26 chữ cái
- Các dấu phép toán số học
- Các dấu phép toán quan hệ
* Các phép toán số học và logic
Các từ sau xem như là các từ khoá : if, else, case, for, while , do while
* Các phép toán số học và logic
- Các phép toán số học : +, -, *, /, %
* Lệnh gán: biến=biểu thức;
* Cấu trúc rẽ nhánh if
Toán tử if cho phép thực hiện lựa chọn giữa hai nhánh dựa trên giá trị của biểu thức, xác định xem nó có bằng không hay không Có hai cách viết của toán tử if: Dạng một là "if (biểu thức) khối lệnh 1", và Dạng hai là "if (biểu thức) khối lệnh 1 else khối lệnh 2".
Sự lồng nhau của các toán tử if :
C cho phép sử dụng các toán tử if lồng nhau có nghĩa là trong các khối lệnh
Các toán tử if - else trong đoạn mã có thể chứa nhiều cấu trúc lồng nhau Nếu không sử dụng dấu ngoặc để phân tách các khối, có thể dẫn đến nhầm lẫn giữa các câu lệnh if-else Cần lưu ý rằng máy sẽ tự động gán toán tử else với toán tử if gần nhất mà không có else.
* Cấu trúc rẽ nhánh - toán tử switch: switch (biểu thức nguyên)
{ case n1 khối lệnh 1 case n2 khối lệnh 2 case nk khối lệnh k [ default khối lệnh k+1]
Trong lập trình, các ni (biến) có thể là các số nguyên, hằng ký tự hoặc biểu thức hằng, và cần có giá trị khác nhau Thân của toán tử switch được xác định bởi đoạn chương trình nằm giữa các dấu { } Thành phần default là tùy chọn và không bắt buộc có trong thân của switch.
* Cấu trúc lặp với toán tử while :
Toán tử while dùng để xây dựng chu trình lặp dạng : while (biểu thức)
Như vậy toán tử while gồm một biểu thức và thân chu trình Thân chu trình có thể là một lệnh hoặc một khối lệnh
Hoạt động của chu trình như sau :
Máy xác định giá trị của biểu thức, tuỳ thuộc giá trị của nó máy sẽ chọn cách thực hiện như sau :
Nếu biểu thức có giá trị 0 (biểu thức sai), máy sẽ ra khỏi chu trình và chuyển tới thực hiện câu lệnh tiếp sau chu trình trong chương trình
Nếu biểu thức trong vòng lặp while có giá trị khác không, máy sẽ thực hiện lệnh hoặc khối lệnh bên trong Sau khi hoàn thành khối lệnh, máy sẽ kiểm tra lại giá trị của biểu thức và tiếp tục thực hiện các bước tương tự.
* Cấu trúc lặp với toán tử for :
Toán tử for dùng để xây dựng cấu trúc lặp có dạng sau : for (biểu thức 1; biểu thức 2; biểu thức 3)
Toán tử for trong lập trình bao gồm ba biểu thức và một thân for, nơi thân for có thể là một câu lệnh hoặc một khối lệnh Mặc dù bất kỳ biểu thức nào trong ba biểu thức có thể không có, nhưng cần phải giữ dấu chấm phẩy (;) giữa các biểu thức.
Biểu thức 1 thường được sử dụng như toán tử gán để khởi tạo giá trị cho biến điều khiển Biểu thức 2 là một quan hệ logic thể hiện điều kiện cần thiết để tiếp tục chu trình Cuối cùng, biểu thức 3 là toán tử gán nhằm thay đổi giá trị của biến điều khiển.
Hoạt động của toán tử for :
Toán tử for hoạt động theo các bước sau :
Tuỳ thuộc vào tính đúng sai của biểu thức 2 để máy lựa chọn một trong hai nhánh :
Nếu biểu thức 2 có giá trị 0 (sai), máy sẽ ra khỏi for và chuyển tới câu lệnh sau thân for
Nếu biểu thức 2 có giá trị khác 0 (đúng), máy sẽ thực hiện các câu lệnh trong thân for
Tính biểu thức 3, sau đó quay lại bước 2 để bắt đầu một vòng mới của chu trình
Khác với các toán tử while và for, chu trình do while kiểm tra điều kiện kết thúc ở cuối, đảm bảo rằng thân của chu trình luôn được thực hiện ít nhất một lần.
Lệnh hoặc khối lệnh; while (biểu thức) ;
Hoạt động của chu trình như sau :
Máy thực hiện các lệnh trong thân chu trình
Sau khi hoàn tất tất cả các lệnh trong thân chu trình, máy sẽ đánh giá giá trị của biểu thức sau từ khóa "while" và quyết định có tiếp tục thực hiện hay không.
Nếu biểu thức đúng (khác 0) máy sẽ thực hiện lặp lại khối lệnh của chu trình lần thứ hai rồi thực hiện kiểm tra lại biểu thức như trên
Nếu biểu thức sai (bằng 0) máy sẽ kết thúc chu trình và chuyển tới thực hiện lệnh đứng sau toán tử while
Những điều lưu ý với toán tử while ở trên hoàn toàn đúng với do while
Câu lệnh break cho phép thoát khỏi các vòng lặp như for, while, do while và switch Khi có nhiều vòng lặp lồng nhau, break sẽ đưa chương trình ra khỏi vòng lặp bên trong nhất mà không cần điều kiện nào.
Lệnh continue, khác với lệnh break, được sử dụng để bắt đầu một vòng mới trong chu trình Trong các cấu trúc lặp như while và do while, lệnh continue sẽ chuyển điều khiển về phần kiểm tra điều kiện, trong khi ở vòng lặp for, điều khiển sẽ quay lại bước khởi đầu để tính biểu thức 3, sau đó tiếp tục với bước 2 để bắt đầu vòng lặp mới Lưu ý rằng lệnh continue chỉ áp dụng cho các chu trình và không có hiệu lực trong cấu trúc switch.
Thiết kế thuật toán 7
1.4.1 Modul hoá và thiết kế từ trên xuống
Các bài toán giải trên máy tính ngày càng phức tạp và đa dạng, đòi hỏi các thuật toán quy mô lớn với nhiều thời gian và công sức Để đơn giản hóa quá trình giải quyết, việc chia bài toán thành các bài toán nhỏ hơn là cần thiết Điều này có nghĩa là bài toán chính cần được phân tách thành các modul con, và các modul con này cũng cần được phân rã thành các modul phù hợp hơn.
Việc tổ chức lời giải theo cấu trúc phân cấp là một chiến thuật "chia để trị", được thể hiện qua thiết kế từ trên xuống Phương pháp này giúp nhìn nhận vấn đề một cách tổng quát, bắt đầu từ các công việc chính và sau đó bổ sung dần các chi tiết cần thiết.
1.4.2 Phương pháp làm mịn dần (tinh chỉnh từng bước) Đầu tiên thuật toán được trình bày dưới dạng ngôn ngữ tự nhiên thể hiện ý chính công việc Các bước sau sẽ chi tiết hóa dần tương ứng với các công việc nhỏ hơn Đó là các bước làm mịn dần đặc tả thuật toán và hướng về ngôn ngữ lập trình mà ta dự định cài đặt
Quá trình thiết kế và phát triển thuật toán diễn ra qua ba giai đoạn chính: bắt đầu từ ngôn ngữ tự nhiên, tiếp theo là ngôn ngữ mã giả, và cuối cùng là ngôn ngữ lập trình Điều này thể hiện sự chuyển biến từ việc xác định "làm cái gì" đến việc cụ thể hóa "làm như thế nào".
1.4.3 Một số kỹ thuật thiết kế
Dựa trên lý thuyết máy Turing, các bài toán được phân thành hai lớp không giao nhau: lớp bài toán có thể giải bằng thuật toán và lớp bài toán không thể giải bằng thuật toán Đối với lớp bài toán có thể giải, có thể xác định một số kỹ thuật thiết kế thuật toán cơ bản dựa vào các đặc trưng của quá trình thiết kế.
1) Kỹ thuật chia để trị
Chia bài toán thành các bài toán đủ nhỏ, giải các bài toán nhỏ rồi tổng hợp kết quả lại
Trong quá trình tìm kiếm, việc xác định ưu tiên cho từng bước của thuật toán là rất quan trọng, có thể là theo chiều rộng hoặc chiều sâu Một ví dụ điển hình là thuật toán giải bài toán 8 hậu, nơi mà việc lựa chọn phương pháp tìm kiếm ảnh hưởng trực tiếp đến hiệu quả giải quyết vấn đề.
3) Kỹ thuật tham lam Ý tưởng là : Xác định trật tự xử lý để có lợi nhất, Sắp xếp dữ liệu theo trật tự đó, rồi xử lý dữ liệu theo trật tự đã nêu Công sức bỏ ra là tìm ra trật tự đó Chẳng hạn thuật toán tìm cây khung nhỏ nhất
4) Kỹ thuật nhánh và cận
Trong quá trình giải quyết bài toán, chúng ta phân chia các phương án thành nhiều tập con, được thể hiện dưới dạng các nút trong cây tìm kiếm Bằng cách sử dụng phép đánh giá cận, chúng ta có thể loại bỏ những nhánh không chứa phương án tối ưu, từ đó tối ưu hóa quá trình tìm kiếm.
5) Kỹ thuật Quy hoạch động
Kỹ thuật quy hoạch động dựa vào một nguyên lý, gọi là nguyên lý tối ưu của Bellman :
“ Nếu lời giải của bài toán là tối ưu thì lời giải của các bài toán con cũng tối ưu ”
Kỹ thuật này áp dụng phương pháp tìm kiếm giải pháp theo cách từ dưới lên, bắt đầu từ những bài toán con nhỏ và đơn giản nhất Bằng cách kết hợp các lời giải của những bài toán này, ta dần dần xây dựng được lời giải cho các bài toán lớn hơn, cho đến khi đạt được lời giải cho bài toán ban đầu.
Khi giải quyết một bài toán, chúng ta có thể áp dụng nhiều thuật toán khác nhau, tuy nhiên, việc đánh giá và lựa chọn thuật toán tốt nhất là rất quan trọng Thông thường, chúng ta dựa vào các tiêu chí nhất định để thực hiện quá trình này.
- Thuật toán thực hiện nhanh
Khi phát triển một chương trình chỉ sử dụng trong một thời gian ngắn, việc chọn thuật toán đơn giản và dễ thực hiện là rất quan trọng Mục tiêu chính là nhanh chóng có được kết quả, do đó thời gian thực hiện chương trình không cần phải được ưu tiên hàng đầu.
Khi một chương trình được sử dụng nhiều lần, việc tiết kiệm thời gian thực hiện trở nên rất quan trọng, đặc biệt với những chương trình cần xử lý dữ liệu lớn Hiệu quả thời gian thực hiện của thuật toán sẽ được xem xét kỹ lưỡng Ngoài ra, với khối lượng dữ liệu lớn và dung lượng bộ nhớ hạn chế, yêu cầu tiết kiệm bộ nhớ cũng không thể bị bỏ qua Tuy nhiên, việc cân bằng giữa yêu cầu về thời gian và không gian thường khó đạt được một giải pháp hoàn hảo.
Sau đây ta sẽ chỉ chú ý đến việc phân tích thời gian thực hiện thuật toán
1.5.1 Thời gian thực hiện thuật toỏn
Một cách để đánh giá hiệu quả thời gian thực hiện của một thuật toán là lập trình nó và đo thời gian thực hiện trên một máy tính cụ thể với một tập hợp dữ liệu đầu vào được chọn lọc.
Thời gian thực hiện thuật toán không chỉ bị ảnh hưởng bởi thuật toán mà còn bởi các chỉ thị của máy tính, chất lượng phần cứng và kỹ năng lập trình viên Sự thi hành có thể được tối ưu hóa cho các tập dữ liệu cụ thể Để giải quyết những thách thức này, các nhà khoa học máy tính đã công nhận tính phức tạp về thời gian như một chỉ số quan trọng trong việc đánh giá hiệu suất của thuật toán Thuật ngữ "tính hiệu quả" thường được sử dụng để chỉ sự đo lường này, đặc biệt là trong trường hợp xấu nhất của phức tạp thời gian.
Thời gian thực hiện thuật toán không chỉ phụ thuộc vào kích thước dữ liệu mà còn vào tính chất của dữ liệu đầu vào Cùng một kích thước dữ liệu, nhưng thời gian thực hiện có thể khác nhau Ví dụ, trong chương trình sắp xếp dãy số nguyên tăng dần, thời gian thực hiện sẽ khác nhau khi dữ liệu đầu vào đã có thứ tự, chưa có thứ tự, hoặc khi dãy số đã được sắp xếp tăng dần so với khi dãy số được sắp xếp giảm dần.
Thành lập phương trình truy hồi 18
Phương trình truy hồi thể hiện mối liên hệ giữa T(n) và T(k), trong đó T(n) là thời gian thực hiện chương trình với kích thước dữ liệu n, và T(k) là thời gian thực hiện với kích thước dữ liệu k (k < n) Để xây dựng phương trình truy hồi, cần dựa vào chương trình đệ quy.
Một chương trình đệ quy để giải bài toán kích thước n cần có ít nhất một trường hợp dừng cho n cụ thể và một lời gọi đệ quy cho bài toán kích thước k (k1 T(n) if (n 1 cần thực hiện lệnh gán gt= n*Giai_thua(n - 1)
Thời gian T(n) được xác định là O(1) cho các phép nhân và gán, cộng với T(n-1) cho lời gọi đệ quy Giai_thua(n – 1) Do đó, ta có mối quan hệ sau: T(n) = O(1) + T(n-1).
Thay các O(1) bởi các hằng nào đó, ta nhận được quan hệ sau
T(n) = C 2 + T(n - 1) Để giải phương trình truy hồi, tìm T(n), chúng ta áp dụng phương pháp thế lặp Ta có phương trình truy hồi
Thay m lần lượt bởi 2, 3, , n - 1, n, ta nhận được các quan hệ sau:
Bằng các phép thế liên tiếp, ta nhận được
T(n) = (n - 1) C 2 + T(1) hay T(n) = (n - 1) C 2 + C 1 , trong đó C 1 và C 2 là các hằng nào đó
Giải phương trình truy hồi sau: c 1 nếu n=1
Quá trình sẽ dừng khi: i
n =2 i i = log 2 n Khi đó: T(n) = nT(1) + c 2 nlog 2 n
Ta đoán một nghiệm f(n) và dùng chứng minh quy nạp để chứng tỏ rằng T(n)
Trong toán học, hàm f(n) thường được xác định cho mọi n và thường thuộc về các hàm quen thuộc như log 2 n, n, n log 2 n, n^2, n^3, 2^n, n!, và n^n Đôi khi, chúng ta chỉ có thể ước lượng dạng của f(n) với một số tham số chưa xác định, ví dụ như f(n) = an^2 với a chưa xác định Trong quá trình chứng minh quy nạp, chúng ta sẽ suy diễn ra giá trị thích hợp cho các tham số này.
Ví dụ 1.10 Giải phương trình truy hồi sau:
Giả sử chúng ta đoán f(n) = anlog2n Với n = 1 ta thấy rằng việc đoán như vậy không được bởi vì anlog2n có giá trị 0 không phụ thuộc vào giá trị của a
Vì thế ta thử tiếp theo f(n) = anlog2n + b
Với n = 1 ta có, T(1) = C1 và f(1) = b, muốn T(1) ≤ f(1) thì b ≥ C1 (*)
Giả sử rằng T(k) ≤ f(k), tức là T(k) ≤ aklog2k + b với mọi k < n (giả thiết quy nạp)
Ta phải chứng minh T(n) ≤ anlog 2 n + b với mọi n
Giả sử n ≥ 2, từ phương trình đã cho ta có T(n) = 2T(
2 n )+ c 2 n Áp dụng giả thiết quy nạp với k 2 n ta có
≤ (anlog 2 n + b) + [b + (c 2 - a)n] Nếu lấy a ≥ c 2 + b (**) ta được
Nếu ta lấy a và b sao cho cả (*) và (**) đều thoả mãn
Tức là: b c1 a c 2 + b thì T(n) ≤ anlog 2 n + b với mọi n
Như vậy với b c 1 và a c 1 + c 2 thì ta sẽ có T(n) ≤ (c 1 + c 2 )nlog 2 n +c 1 với mọi n Hay nói cách khác T(n) là O(nlog 2 n)
* Phương pháp dùng phương trình đặc trưng với phương trình truy hồi tuyến tính thuần nhất hệ số hằng
Phương trình truy hồi (công thức truy hồi) tuyến tính thuần nhất bậc k với hệ số hằng số có dạng:
T(n) a n = c 1 a n-1 + c 2 a n-2 + + c k a n-k trong đó c 1 , c 2 , , c k là các số thực, c k 0
Nếu được cung cấp các điều kiện ban đầu a0 = c0, a1 = c1, , ak-1 = ck-1, thì theo nguyên tắc quy nạp toán học, dãy số thỏa mãn phương trình truy hồi trong định nghĩa sẽ được xác định một cách duy nhất.
Phương pháp cơ bản để giải phương trình truy hồi tuyến tính thuần nhất là tìm nghiệm dưới dạng a_n = r^n, với r là hằng số Nghiệm a_n = r^n thỏa mãn phương trình truy hồi a_n = c_1 a_{n-1} + c_2 a_{n-2} + + c_k a_{n-k khi và chỉ khi điều kiện r^n = c_1 r^{n-1} + c_2 r^{n-2} + + c_k r^{n-k được thỏa mãn Do đó, ta có phương trình r^n - c_1 r^{n-1} - c_2 r^{n-2} - - c_k r^{n-k = 0.
Dãy số {an} với a n = r n là nghiệm của phương trình đại số khi và chỉ khi r là nghiệm của phương trình đặc trưng, được gọi là nghiệm đặc trưng của công thức truy hồi Các nghiệm này là cơ sở để tìm công thức tường minh cho tất cả các nghiệm của phương trình truy hồi Đối với phương trình truy hồi tuyến tính thuần nhất bậc 2, nếu phương trình đặc trưng có hai nghiệm phân biệt r 1 và r 2, thì dãy số {an} là nghiệm của công thức truy hồi a n = c 1 a n-1 + c 2 a n-2 khi và chỉ khi a n = 1 r 1 n + 2 r 2 n, với n = 0, 1, 2, , trong đó 1 và 2 là các hằng số.
Giả sử {an} là một nghiệm của phương trình truy hồi, ta chọn 1 và 2 sao cho dãy {an} với a n = a 1 r 1 n + a 2 r 2 n thỏa mãn điều kiện đầu a 0.
Từ phương trình đầu ta được 2 = c 0 - 1 Thay vào phương trình sau ta được: c 1 = a 1 r 1 + (c 0 - 1 )r 2 = a 1 (r 1 - r 2 ) + c 0 r 2
Khi lựa chọn các giá trị a1 và a2, dãy {an} với công thức an = a1 r1^n + a2 r2^n sẽ thỏa mãn các điều kiện đầu Do phương trình truy hồi cùng các điều kiện đầu xác định duy nhất, ta có thể khẳng định rằng an = a1 r1^n + a2 r2^n.
Giả sử rằng các con thỏ không bao giờ chết, một cặp thỏ sẽ sinh ra một cặp thỏ mới sau 2 tháng và tiếp tục sinh thêm mỗi tháng Nếu bắt đầu với một cặp thỏ, số lượng cặp thỏ vào tháng thứ n sẽ tăng theo quy luật sinh sản này.
Số cặp thỏ trong tháng thứ n được ký hiệu là Fn, với điều kiện F1 = F2 = 1 Đối với n > 2, số cặp thỏ trong tháng n sẽ bằng tổng số cặp thỏ của tháng n-1 và tháng n-2.
Fn -1 ) cộng với số cặp thỏ mới được sinh ra ở tháng thứ n - chính là số cặp thỏ có ở tháng thứ n-2 (là Fn -2 ) Tức là:
Vì vậy có thể tính Fn theo hệ thức truy hồi sau:
Dãy số thể hiện Fn với các giá trị của n được gọi là dãy số Fibonacci
Từ hệ thức truy hồi trên ta dễ dàng có được giải thuật sau để tính số cặp thỏ có ở tháng thứ n
{ if(n2 T(n) Giải phương trình đặc trưng r 2 - r- 1 = 0 ta thu được hai nghiệm:
Khi đó ta có T(n) = 1 r 1 n + 2 r 2 n (*) trong đó 1 , 2 là các hằng số cần xác định từ các giá trị ban đầu T(1) và T(2) Thay T(1) và T(1) vào (*) và giải ra ta được
Như vậy độ phức tạp tính toán của giải thuật là cấp hàm mũ
Trong bài viết này, chúng tôi trình bày các phương pháp giải phương trình truy hồi, bao gồm hệ thức và công thức truy hồi Những cách giải này giúp người đọc dễ dàng áp dụng để xác định độ phức tạp tính toán của các thuật toán tương ứng.
Tìm nghiệm của công thức truy hồi a n = a n-1 + 2a n-2 , với a 0 = 2, a 1 = 7
Phương trình đặc trưng của công thức truy hồi có dạng r² - r - 2 = 0, với nghiệm r = 2 và r = -1 Theo định lý, dãy {an} là nghiệm của công thức truy hồi khi và chỉ khi an = α₁ * 2ⁿ + α₂ * (-1)ⁿ, với các hằng số α₁ và α₂ Từ các điều kiện ban đầu, ta có a₀ = 2 = α₁ + α₂ và a₁ = 7 = α₁ * 2 + α₂ * (-1).
Giải ra ta được 1 = 3 và 2 = -1 Vậy nghiệm của công thức truy hồi với điều kiện đầu là dãy {an} với an = 3.2 n - (-1) n
Khi phương trình đặc trưng của công thức truy hồi tuyến tính thuần nhất bậc 2 có nghiệm đặc trưng bội (chỉ có một nghiệm r0), dãy số {an} sẽ là nghiệm của công thức truy hồi an = c1 a n-1 + c2 a n-2 nếu và chỉ nếu an = α1 r0^n + α2 n r0^n với n = 0, 1, 2, , trong đó α1 và α2 là các hằng số.
Tìm nghiệm của hệ thức truy hồi a n = 6a n-1 - 9a n-2 với các điều kiện ban đầu a 0 = 1 và a 1 =6
Phương trình đặc trưng r² - 6r + 9 = 0 có nghiệm kép r = 3, dẫn đến nghiệm của hệ thức truy hồi có dạng an = α₁ * 3^n + α₂ * n * 3^n Với điều kiện đầu a₀ = 1 và a₁ = 6, ta suy ra α₁ = 1 và α₂ = 1 Do đó, nghiệm của hệ thức truy hồi cùng với các điều kiện ban đầu là: aₙ = 3^n + n * 3^n.
Khi tổng quát hóa kết quả cho hệ thức truy hồi tuyến tính thuần nhất với hệ số hằng bậc k > 2, giả sử phương trình đặc trưng rk - c1 rk -1 - c2 rk -2 - - ck = 0 có k nghiệm phân biệt r1, r2, , rk Dãy số {an} sẽ là nghiệm của hệ thức truy hồi an = c1 an-1 + c2 an-2 + + ck an-k nếu và chỉ nếu an = α1 r1^n + α2 r2^n + + αk rk^n với n = 0, 1, 2, , trong đó α1, α2, , αk là các hằng số.
Tìm nghiệm của hệ thức a n = 6a n-1 - 11a n-2 + 6a n-3 với điều kiện đầu a 0 = 2, a 1
Giải: Phương trình đặc trưng r 3 - 6r 2 + 11r- 6 = 0 có 3 ngiệm r 1 = 1, r 2 = 2, r 3 = 3 Vì vậy, nghiệm có dạng a n = 1 1 n + 2 2 n + 3 3 n
Sử dụng các điều kiện đầu ta có 1 =1, 2 =-1, 3 = 2 Vậy nghiệm của hệ thức đã cho là an = 1- 2 n +2.3 n
* Phương trình truy hồi có dạng:
(1 Để xác định độ phức tạp tính toán của thuật toán theo phương trình truy hồi trên ta thực hiên như sau: