Thuật Toán Và Độ Phức Tạp Của Thuật Toán

Thuật toán (algorithm) là một trong những khái niệm quan trọng trong lĩnh vực tin học. Thuật ngữ thuật toán được xuất phát từ nhà toán học Arập Abu Ja’far Mohammed ibn Musa al Khowarizmi (khoảng năm 825). Tuy nhiên lúc bấy giờ và trong nhiều thế kỷ sau, nó không mang nội dung như ngày nay chúng ta quan niệm. Thuật toán nổi tiếng nhất có từ thời cổ Hy lạp là thuật toán Euclid., thuật toán tìm ước chung lớn nhất của hai số nguyên . Có thể mô tả thuật toán đó như sau:

 Thuật toán Euclid .

Input: m, n nguyên dương

Output: g  (ước chung lớn nhất của m và n)

Phương pháp:

Bước 1: Tìm r, phần dư của m cho n

Bước 2: Nếu r = 0, thì g:=n (gán giá trị của n cho g),và dừng lại. Trong trường hợp ngược lại (r¹0) ,thì  m:=n; n:=r và quay lại bước 1.

Chúng ta có thể quan niệm các bước cần thực hiện để làm một món ăn, được mô tả trong các sách dạy chế biến món ăn, là một thuật toán . Cũng có thể xem các bước cần tiến hành để gấp đồ chơi bằng giấy ,được trình bày trong sách dạy gấp đồ chơi bằng giấy là một  thuật toán. Phương pháp cộng nhân các số nguuyên, chúng ta đã được học ở cấp I cũng là các thuật toán.

Vì vậy ta có định nghĩa không hình thức về thuật toán như sau:

Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán, hoặc hành động cần thực hiện ... để cho ta lời giải của bài toán.

Định nghĩa trên về thuật toán tất nhiên còn chứa nhiều điều chưa rõ ràng. Để hiểu đầy đủ ý nghĩa của khái niệm thuật toán ,chúng ta đưa ra 5 đặc trưng sau đây của thuật toán.  

1. Input

Mỗi thuật toán đều có một số (có thể bằng không ) các dữ liệu vào (input) . Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu này cần được lấy từ các tập hợp giá trị cụ thể nào đó. Chẳng hạn, trong thuật toán Euclid ở trên, các số  m và n là các dữ liệu lấy từ tập các số nguyên  dương .

2. Output

Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output). Đó là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào, và là kết quả của sự thực hiện thuật toán .Trong thuật toán Euclid, có một dữ liệu ra đó là ƯSCLN g, khi thuật toán dừng lại (trường hợp r=0) thì giá trị của g là ước chung lớn nhất của m và n.

3. Tínhxác định.

ở mỗi bước ,các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn là trong cùng một điều kiện hai bộ xử lý cùng thực hiện một thuật toán phải cho cùng một kết quả như nhau.Nếu biểu diễn thuật toán bằng phương pháp thông thường không có gì đảm bảo được ngươì đọc hiểu đúng ý của người viết thuật toán. Để đảm bảo đòi hỏi này, thuật toán cần được mô tả trong các ngôn ngữ lập trình (ngôn ngữ máy,hợp ngữ hoặc ngôn ngữ bậc cao như Pascal..  ). Trong các ngôn ngữ này các mệnh đề được tạo theo các qui tắc cú pháp nghiêm ngặt và chỉ có  một nghĩa duy nhất .

4. Tính khả thi/đa năng .

Tất cả các phép toán có mặt trong thuật toán phải đủ đơn giản . Điều đó có nghĩa là, các phép toán phải sao cho, ít nhất về nguyên tắc có thể thực hiện bởi con người chỉ bằng giấy trắng và bút chì trong một khoảng thời gian hữu hạn. Chẳng hạn, trong thuật toán Euclid ta chỉ cần thực hiện các phép chia các số nguyên, các phép gán và các phép so sánh r=0 hay  r ¹ 0. Điều quan trọng nữa là thuật toán phải có tính đa năng làm việc được với tất cả các tập hợp dữ liệu có thể của đầu vào.

5. Tính dừng.

Với mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ liệu vào (tức là được lấy ra từ các tập của dữ liệu vào), thuật toán phải dừng lại sau một số hữu hạn bước thực hiện.Ví dụ, thuật toán Euclid thoả mãn điêù kiện này. Bởi vì giá trị của r luôn nhỏ hơn n (khi thực hiện bước 1), nếu r <>0 thì giá trị của n ở bước i (ký hiệu là ni) sẽ là gía trị của ri_-1 ở bước i-1, ta phải có bất đẳng thức n>r =n₁>r₁ = n₂ > r₂. Dãy số nguyên dương này giảm dần và cần phải kết thúc ở 0, do đó sau một số hữu hạn bước nào đó giá trị của r phải = 0 và thuật toán phải dừng lại.

Với một vấn đề đặt ra ,có thể có một hoặc nhiều thuật toán giải .Một vấn đề có thuật toán giải gọi là vấn đề giải được (bằng thuật toán). Chẳng hạn, tìm nghiệm của hệ phương trình tuyến tính  là vấn đề giải được. Một vấn đề không tồn tại thuật toán gọi là vấn đề không giải được (bằng thuật toán).  Một trong những thành tựu suất xắc nhất của toán học thế kỷ 20 là đã tìm ra những vấn đề không giải được bằng thuật toán. Chẳng hạn thuật toán chắc thắng cho người thứ hai của cờ ca rô hoặc thuật toán xác định xem một máy Turing có dừng lại sau n bước  không, đềulà những vấn đề không tồn tại thuật toán giải được.  

Để giải một bài toán trên máy tính điện tử (MTĐT) ,điều trước tiên là chúng ta phải có thuật toán. Một câu hỏi đặt ra là làm thế nào để tìm ra được thuật toán cho một bài toán đã đặt ra? Lớp các bài toán được đặt ra từ các ngành khoa học kỹ thuật, từ các lĩnh vực hoạt động của con người là hết sức phong phú và đa dạng. Các thuật toán giải các lớp bài toán khác nhau cũng rất khác nhau. Tuy nhiên ,có một số kỹ thuật thiết kế thuật toán chung như: Chia để trị (divide-and-conque), phương pháp tham ăn (greedy method), qui hoạch động (dynamic programming)... Việc nắm được các chiến lược thiết kế  thuật toán này là hết sức quan trọng và cần thiết vì nó giúp cho ta dễ tìm ra các thuật toán mới cho các bài toán mới được đưa ra.

Khi một thuật toán được làm ra, ta cần phải chứng minh rằng ,thuật toán khi được thực hiện sẽ cho ta kết quả đúng với mọi dữ liệu vào hợp lệ. Điều này gọi là chứng minh tính đúng đắn của thuật toán. Việc chứng minh tính đúng đắn của thuật toán là một công việc không dễ dàng. Trong nhiều trường hợp, nó đòi hỏi ta phải có trình độ và khả năng tư duy toán học tốt.

Sau đây ta sẽ chỉ ra rằng, khi thực hiện thuật toán Euclid, g sẽ là ước chung lớn nhất của hai số nguyên dương bất kỳ m,n. Thật vậy , khi thực hiện bước 1 ,ta có m = qn + r ,trong đó q là số nguyên nào đó . Nếu r = 0 thì n là ước của m và hiển nhiên n (do đó g) là ước chung lớn nhất của m và n. Nếu r 0 thì một ước chung bất kỳ của m và n cũng là ước chung của n và r (vì r=m-qn). Ngược lại một ước chung bất kỳ của n và r cũng là ước chung của m và n (vì m = qn + r). Do đó ước chung lớn nhất của n và r cũng là ước chung lớn nhất của ma và n. Vì vậy, khi thực hiện lặp lại bước 1, với sự thay đổi giá trị của m bởi n, và sự thay đổi giá trị của n bởi r, cho tới khi r=0 ta nhận được giá trị của g là ước chung lớn nhất  của các giá trị m và n ban đầu.

Khi giải một vấn đề ,chúng ta cần chọn trong số các thuật toán, một thuật toán mà chúng ta cho là “tốt” nhất .Vậy ta cần lựa chọn thuật toán dựa trên cơ sở nào? Thông thường ta dựa trên hai tiêu chuẩn sau đây:

1. Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)
2. Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính, và đặc biệt chạy nhanh nhất có thể  được.

Khi ta viết một chương trình chỉ để sử dụng một số ít lần ,và cái giá của thời gian viết chương trình vượt xa cái giá  của chạy chương trình  thì tiêu chuẩn (1) là quan trọng nhất . Nhưng có trường hợp ta cần viết các chương trình (hoặc thủ tục, hàm) để sử dụng nhiều lần , cho nhiều người sử dụng , khi đó giá của thời gian chạy chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các thủ tục sắp xếp ,tìm kiếm được sử dụng rất nhiều lần, bởi rất nhiều người trong các bài toán khác nhau . Trong trường hợp này ta cần dựa trên tieu chuẩn 2. Ta sẽ cài đặt thuật táon có thể sẽ rất phức tạp , miễn là chương trình nhận được chạy nhanh hơn so với các chương trình khác.

Tiêu chuẩn 2 được xem là tính hiệu quả của thuật toán. Tính hiệu quả của thuật toán bao gồm hai nhân tố cơ bản:

Dung lượng không gian nhớ cần thiết để lưu giữ các giữ liệu vào , các kết quả tính toán trung gian và các kết quả của thuật toán .

Thời gian cần thiết để thực hiện thuật toán (ta gọi là thời gian chạy). Chúng ta chỉ quan tâm đến thời gian thực hiện thuậ toán, có nghĩa là ta nói đến đánh giá thời gian thực hiện. Một thuật toán có hiệu quả được xem là thuật toán có thời gian chạy ít hơn so với các thuật toán khác.

Bài tập

1. Xác định số phép tính so sánh nhiều nhất có thể trong thuật toán của bạn tìm phần tử lớn nhất của một dãy n số thực cho trước.
2. Xác định số phép tính so sánh nhiều nhất có thể trong thuật toán của bạn để xếp lại một dãy có n số thực theo thứ tự tăng dần.
3. Xác định số bước thực hiện nhiều nhất có thể trong thuật toán của bạn nhằm xác định được nhiều nhất có thể các số liên tiếp nhau có tổng dương trong một dãy n số hạng cho trước .

Có nhiều phương pháp biểu diễn thuật toán .Có thể biểu diễn thuật toán bằng danh sách các bước, các bước được diễn đạt bằng ngôn ngữ thông thường và các ký hiệu toán học. Có thể biểu diễn thuật toán bằng sơ đồ khối. Tuy nhiên, để đảm bảo tính xác định của thuật toán như đã trình bày trên, thuật toán cần được viết trên các ngôn ngữ lập trình. Một chương trình là sự biểu diễn của một thuật toán trong ngôn ngữ lập trình đã chọn. Thông thường ta dùng ngôn ngữ lập trình Pascal, một ngôn ngữ thường được chọn để trình bày các thuật toán trong sách báo.

Ngôn ngữ thuật toán là ngôn ngữ dùng để miêu tả thuật toán .Thông thường ngôn ngữ thuật toán bao gồm ba loại:

      + Ngôn ngữ liệt kê từng bước;

      + Sơ đồ khối;

      + Ngôn ngữ lập trình;

Ngôn ngữ liệt kê từng bước nội dung như sau:

Thuật toán: Tên thuật toán và chức năng.

Vào: Dữ liệu vào với tên kiểu.

Ra: Các dữ liệu ra với tên kiểu.

 Biến phụ (nếu có) gồm tên kiểu.

Hành động là các thao tác với các lệnh có nhãn là các số tự nhiên.

Ví dụ. Để giải  phương trình bậc hai ax² + bx +c = 0, ta có thể mô tả thuật toán bằng ngôn ngữ liệt kê như sau:

Bước 1: Xác định các hệ số a,b,c.

Bước 2 :Kiểm tra xem các hệ số a,b,c có khác 0 hay không ?

Nếu a=0 quay lại thực hiện bước 1.

Bước 3: Tính biểu thức   = b² – 4*a*c.

Bước 4:Nếu D <0 thông báo phương trình vô nghiệm và chuyển sang bước 8. 

Bước 5:Nếu D=0,tính x₁=x₂=  và chuyển sang bước 7.

Bước 6: Tính x₁=  , x₂=  và chuyển sang bước 7.

Bước 7: Thông báo các nghiệm x₁ , x₂ .

Bước 8: Kết thúc thuật toán.

Phương pháp dùng sơ đồ khối mô tả thuật toán là dùng mô tả theo sơ đồ trên mặt phẳng các bước của thuật toán. Sơ đồ khối có ưu điểm là rất trực giác dễ bao quát.

Để mô tả thuật toán bằng sơ đồ khối ta cần dựa vào các nút sau đây:

                  Nút thao tác:Biểu diễn bằng hình chữ nhật,

         Nút điều khiển: Được biểu diễn bằng hình thoi,trong đó ghi điều kiện cần kiểm tra trong quá trình tính toán.

                 Nút khởi đầu ,kết thúc: Thường được biểu diễn bằng hình tròn thể hiện sự bắt đầu hay kết thúc quá trình.

                  Cung :Đoạn nối từ nút này đến nút khác và có mũi tên chỉ hướng .

                                                                            Bài tập

1. Mô tả các thuật toán của bạn bằng sơ đồ khối:
2. a) Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn số thực.
3. b) Thuật toán tìm phần tử bé nhất của một tập con của tập hợp.
4. c) Thuật toán xếp lại một dãy theo thứ tự tăng dần.
5. d) Thuật toán tìm một dãy các số liên tiếp nhau (dài nhất có thể) có tổng dương trong một dãy số thực cho trước.

Ngôn ngữ tựa Pascal được sử dụng dùng để mô tả các bước của thuật toán. Nó có đặc điểm là giúp mô tả thuật toán gần gũi với một chương trình máy tính và làm mô tả thuật toán trở nên chính xác hơn. Dưới đây là liệt kê một số câu lệnh chính được sử dụng để mô tả thuật toán dùng ngôn ngữ lập trình Pascal:

Ký tự và biểu thức

Các ký tự la tinh :A, a, ..., Z, z. Chữ số :0…9.

Các phép toán số học : + , - , * , /

Các phép toán quan hệ : < , > , = ,

Giá trị logic : T (true) , F (false)

Phép toán logic : and , or , not

Hằng đó là các giá trị cụ thể nào đó

Tên biến :Là một dãy kí tự mà kí tự đầu phải là chữ cái.

Có hai loại biến chính :

            Loại integer (biến nguyên ). Ví dụ Var bien : integer;

            Loại Real (biến thực) .Ví dụ var bien real;

Biến  chỉ số . Ví dụ A  . ở đây i là các biến nguyên.

Biểu thức là kết hợp các hằng ,biến và các phép tóan.

Kỹ thuật máy tính tiến bộ rất nhanh, ngày nay các máy tính lớn có thể đạt tốc đọ tính toán hàng trăm triệu phép tính một giây. Vởy thì có bõ công phải tiêu tốn thời gian để thiết kế các thuật toán có hiệu quả không ? Ví dụ sau đây sẽ trả lời  câu  hỏi này.

Ví dụ: Bài toán tháp Hà Nội.

Có 3 cọc A,B,C. Lúc đầu ,ở cọc A có n đĩa được lồng theo thứ tự nhỏ dần từ thấp lên cao. Đòi hỏi phải chuyển n đĩa từ cọc A sang cọc B, được quyền sử dụng cọc C làm vị trí trung gian , nhưng không được phép đặt đĩa lớn lên trên dĩa nhỏ.

Để chuyển n đĩa từ cọc A sang cọc B ta cần thực hiện thủ tục sau :đầu tiên là chuyển n-1 đĩa từ cọc A sang cọc C, sau đó chuyển đĩa lớn nhất từ cọc A sang cọc B .Đến đây chỉ cần chuyển n-1 đĩa từ cọc C sang cọc B. Việc chuyển  n-1 đĩa từ cọc này sang cọc kia được thực hiện bằng cách áp dụng đệ qui thủ tục trên.

procedure Move(n,A,B,C);

(*thủ tục chuyển n đĩa từ cọc A sang cọc B*)

begin

if n=1 then chuyển 1 đĩa từ cọc A sang cọc B

            else

      begin

            Move(n-1,A,C,B);

            Chuyển 1 đĩa từ cọc A sang cọc B;

            Move(n-1,C,B,A);

      End;

End;

Trong ví dụ trên ,ta thử tính xem cần thực hiện bao nhiêu lần chuyển đĩa từ cọc này sang cọc khác (không đặt đĩa to lên  trên đĩa nhỏ) để chuyển được n đĩa từ cọc A sang cọc B .Gọi số đó là F(n). Từ thuật toán ta có:

F(1) = 1,

F(n) = 2F(n-1) +1 với n>1.

F(1)=1; F(2)=3; F(3) = 7; với n=1,2,3.

Bằng cách qui nạp ta chứng minh được F(n) = 2ⁿ – 1.

Với n=64, ta có F(64) = 2⁶⁴ –1 lần chuyển. Giả sử mỗi lần chuyển 1 đĩa từ cọc này sang cọc kia, cần 1 giây. Khi đó để thực hiện 2⁶⁴ –1 lần chuyển cần 5.10¹¹ năm. Nếu tuổi của vũ trụ là 10 tỉ năm ,ta cần 50 lần tuổi của vũ trụ để chuyển 64 đĩa !

Đối với một vấn đề có thể có nhiều thuật toán , trong số đó có thể thuật toán này hiệu quả hơn thuật toán kia (chạy nhanh hơn). Tuy nhiên cũng có những vấn đề không tồn tại thuật toán hiệu quả, tức là có thuật toán song thời gian thực hiện nó là quá lớn,trong thực tế không thể thực hiện được, dù là trên các máy tính lớn hiện đại nhất.

Có hai cách tiếp cận để đánh giá thời gian thực hiện của một thuật toán.Trong phương pháp thử nghiệm chúng ta viết chương trình và cho chạy chươn trình với các dữ liệu vào khác nhau trên một máy tính nào đó. Thời gian chạy chương trình phụ thuộc vào các nhân tố sau đây:

1. Các dữ liệu vào
2. Chương trình dịch để chuyển chương trình thành mã máy.
3. Tốc độ thực hiện các phép toán của máy tính được sử dụng để chạy chạy chương trình .

Vì thời gian chạy chương trình phụ thuộc vào nhiều nhân tố, nên ta không thể biểu diễn chính xác thời gian chạy là bao nhiêu đơn vị thời gian chuẩn, chẳng hạn nó là bao nhiêu giây .

Trong phương pháp lí thuyết, ta sẽ coi thời gian thực hiện thuật toán như là hàm số của cỡ dữ liệu vào. Cỡ của dữ liệu vào là một tham số đặc trưng cho dữ liệu vào , nó có ảnh hưởng quyết định đến thời gian thực hiện chương trình. Cái mà chúng ta chọn làm cỡ dữ liệu vào phụ thuộc vào các thuật toán cụ thể .Đối với các thuật toán sắp xếp mảng, cỡ của dữ liệu là số thành phần của mảng. Đối với thuật toán giải hệ n phương trình tuyến tính với n ẩn, ta chọn n là cỡ. Thông thường cỡ của dữ liệu vào là một số nguyên dương n. Ta sẽ sử dụng hàm số T(n), trong đó n là cỡ dữ liệu vào ,để biểu diễn thời gian thực hiện của một thuật toán.

Thời gian thực hiện thuật toán nói chung không những phụ thuộc vào dữ liệu vào, mà còn phụ thuộc vào dữ liệu vào cá biệt .Chẳng hạn,ta xét bài toán xác định một đối tượng a có trong danh sách n phần tử (a₁, a₂,….an ) hay không .Thuật toán ở đây là , so sánh số a với từng phần tử có trong danh sách đi từ  đầu đến cuối danh sách , khi gặp phần tử  aI đầu tiên  thoả mãn aI = a thì dừng lại ,hoặc khi đi đến hết danh sách mà không gặp aI nào bằng a thì trong trường hợp này a không có trong danh sách. Các dữ liệu vào là a và danh sách (a_{1 ,},a₂ , ... .an) (có thể biểu diễn danh sách bằng mảng chẳng hạn). Cỡ của dữ liệu vào là n. Nếu a₁ =a chỉ cần một phép so sánh. Nếu a₁ a ,a₂=a thì cần 2 phép so sánh. Còn nếu aI a (i=1..n-1) và an = a, hoặc a không có trong danh sách, ta cần n phép so sánh. Nếu xem thời gian thực hiện T(n) là số các phép toán so sánh , ta có T(n)  n, trong trường hợp  xấu nhất

T(n)=n Trong các trường hợp như thế, ta nói đến thời gian thực hiện thuật toán trong trường hợp xấu nhất (tốt nhất).

Ngoài ra chúng ta còn sử dụng khái niệm thời gian thực hiện trung bình. Đó là thời gian trung bình Ttb(n) trên tất cả các dữ liệu vào cỡ n .Nói chung thời gian thực hiện trung bình khó xác định hơn thời gian thực hiện trung bình trong trường hợp xấu nhất.

Chúng ta có thể xác định thời gian thực hiện T(n) là số phép toán sơ cấp cần phải tiến hành khi thực hiện thuật toán . Các phép toán sơ cấp là các phép là các phép toán mà thời gian thực hiện bị chặn trên bởi một hằng số chỉ phụ thuộc vào cách cài đặt được sử dụng (ngôn ngữ lập trình ,máy tính...) Chẳng hạn , các phép toán số học +, - , *,/ , các phép toán so sánh  =, < , > , £, ³ là các phép toán sơ cấp . Phép toán so sánh hai xâu ký tự không thể xem là phép toán sơ cấp , vì thời gian thực hiện nó phụ thuộc vào chiều dài của xâu.

Khi đánh giá thời gian thực hiện bằng phương pháp toán học , chúng ta sẽ bỏ qua nhân tố phụ thuộc vào cách cài đặt chỉ tập trung vào xác định độ lớn của thời gian thực hiện T(n).

Giả sử n là số nguyên không âm. T(n) và f(n) là các hàm thực không âm. Ta viết T(n)=O(f(n)) (đọc T(n) là ô lớn của f(n)), nếu và chỉ nếu tồn tại các hằng số dương c và no sao cho T(n) £ c.f(n) ,với mọi n ³ no .

Nếu một thuật toán có thời gian thực hiện T(n) = O(f(n)) , ta nói thuật toán có thời gian thực hiện cấp f(n) .Từ định nghĩa ký hiệu ô lớn , ta có thể xem rằng hàm f(n) là cận trên của T(n).

Ví dụ. Giả sử T(n) = 3n² + 4n +5. Ta có

3n² + 4n + 5 £ 3n² + 4n²  + 5n² = 12n² , với mọi n ³1.

Vậy  T(n) = O(n²) . Trong trường hợp này ta nói thuật toán có thời gian thực hiện cấp n², hoặc gọn hơn , thuật toán có thời gian thực hiện bình phương .

Dễ dàng thấy được, nếu T(n)= O(f(n)) và f(n)= O(f₁(n)), thì T(n) = O(f₁(n)). Thật vậy , vì T(n) là ô lớn của f(n) và f(n) là ô lớn của f₁(n) nên tồn tại các hằng số co , no_, ,c₁, n₁ sao cho T(n)  c₀ f(n) với mọi n  n₀ và f(n)  c₁ f₁(n) với mọi n  n₁ . Từ đó ta có T(n)  c₀c₁f₁(n) với mọi n  max(n₀, n₁).

Khi biểu diễn cấp của thời gían thực hiện thuật toán bởi hàm f(n), chúng ta sẽ chọn f(n) là hàm nhỏ nhất , đơn giản nhất có thể được sao cho       T(n) = 0(f(n)). Thông thường f(n) là các hàm số sau đây: f(n)=1 ; f(n)= logn; f(n) =n; f(n) = nlog(n) ; f(n)= n² ; n³ … ; f(n) = 2ⁿ .

Nếu T(n)= O(1) điều này có nghĩa là thời gian thực hiện thuật toán được chặn trên bởi một hằng nào đó , trong trường hợp này ta nói thuật toán có thời gian thực hiện hằng .

Nếu T(n)= O(n), tức là bắt đầu từ một n₀ nào đó trở đi ta có T(n) £ cn với một hằng số c nào đó , trong trường hợp này ta nói thuật toán có thời gian thực hiện tuyến tính.

Bảng sau đây cho ta các cấp thời gian thực hiện thuật toán được sử dụng rộng rãi  nhất và tên gọi của chúng .

                                                                     Bảng 1

Danh sách trên sắp xếp theo thứ tự tăng dần của hàm thời gian thực hiện.

Để thấy rõ sự khác nhau của thời gian thực hiện các thuật toán ta xét   dụ sau: Giả sử đối với một vấn đề nào đó , ta có hai thuật toán giải A và B. Thuật toán A có thời gian thực hiện là TA(n) = O(n²) thuật toán B có thời gian thực hiện là TB = O(nlogn). Với n= 1024 thuật toán A cần 1048576 phép toán sơ cấp , còn thuật toán B đòi hỏi  10240 phép toán sơ cấp. Nếu cần  một micro-giây cho một phép toán sơ cấp thì thuật toán A cần khoảng 1,05 giây trong khi đó thuật toán B cần khoảng 0,01 giây. Nếu n= 1024 2 , thì thuật toán A đòi hỏi khoảng 4,2  giây ,trong khi thuật toán B chỉ đòi hỏi khoảng 0,02 giây. Với n càng lớn thì thuật toán A càng đòi hỏi thời gian thực hiện nhiều hơn rất nhiều so với thuật toán B. Vì vậy nếu một thuật toán có thời  gian thực hiện O(n²) mà ta tìm ra được một thuật toán khác cho bài toán đó với thời gian O(nlogn) thì đó là một kết quả đáng kể , rất có ý  nghĩa.

Những  thuật toán có thời gian thực hiện cấp nk với k  là một số nguyên và k ³1 thì được gọi là các thuật toán có thời gian thực hiện đa thức.

Sau đây là qui tắc cần thiết về ô lớn để đánh giá thời gian thực hiện thuật toán.

Qui tắc tổng : Nếu T₁(n)=O(f₁(n)) và T₂(n) = O(f₂(n)) thì 

            T₁(n) + T₂(n) = O(max (f₁(n) , f₂(n))).

Thật vậy ,  vì T₁(n) , T₂(n) lần lượt là ô lớn của f₁(n) và f₂(n) tương ứng do đó tồn tại hằng số c₁ , c₂  ,n_{1 ,},n₂ sao cho T₁(n) £ c₁f₁(n) ,T₂(n) £ c₂f₂(n) với mọi n ³ n₁ , mọi n ³ n₂ .Đặt n₀ = max (n₁,n₂) . Khi đó, với mọi n ³ n₀ ta có bất đẳng thức sau         

T₁(n) + T₂(n) £ (c₁ + c₂) max (f₁(n), f₂(n)).

Qui tắc này thường được áp dụng như sau .Giả sử thuật toán của ta được phân thành ba phần tuần tự . Phần một có thời gian thực hiện T₁(n) được đánh giá là O(1), phần hai có thời gian thực hiện là T₂(n) và có thời gian đánh gía là O(n²), phần ba có thời gian thực hiện T₃(n) có thời gian đánh giá là O(n) .Khi đó thời

gian thực hiện thuật toán là T(n) =  T₁(n) + T₂(n) + T₃(n) là O(n²) ,vì n² = max(1, n², n).

Trong sách báo quốc tế các sách báo thường được trình bày dưới dạng các thủ tục hoặc hàm trong ngôn ngữ tựa Pascal. Để đánh giá thời gian thực hiện thuật toán ta cần biết cách đánh giá thời gian thực hiện các câu lệnh trong Pascal, các câu lệnh trong Pascal được định nghĩa đệ qui như sau:

1. Các phép gán ,đọc , viết , goto là câu lệnh .Các lệnh này được gọi là các lệnh đơn .

Thời gian thực hiện các lệnh đơn là  O(1).

2. Nếu S₁, S₂, ..... ,Sn là câu lệnh thì        

        begin  S₁, S₂, .... ,Sn end

là câu lệnh.

Lệnh này được gọi là lệnh hợp thành (hoặc khối).

Thời gian thực hiện lệnh hợp thành được xác định bởi luật tổng .

3. Nếu S₁ ,S₂ là các câu lệnh và E là biểu thức logíc thì :

If E then S₁ else S₂ 

Và

if E then S₁  

là câu lệnh. Các lệnh này được gọi là lệnh if.

Đánh giá thời gian thực hiện các lệnh if  : Giả sử thời gian thực hiện các lệnh S₁,S₂, là O(f₁(n)) và O(f₂(n)) tương ứng .Khi đó thời gian thực hiện lệnh if là : O(max(f₁(n),f₂(n))).

4. Nếu S₁,S₂, .... ,Sn là các câu lệnh , E là biểu thức có kiểu thứ tự đếm được, và v₁,v₂, .... , vn là các giá trị có cùng kiểu với E thì  :

Case   E    of

      v₁:   S₁ ;

      v₂:   S₂ ;

      .............

      vn :   Sn_;;

end;

là các lệnh.

Lệnh này được gọi là lệnh case.

      Đánh gía thời gian thực hiện lệnh case như lệnh if

5. Nếu S  là các câu lệnh và E là biểu thức logíc thì

            While E do S

      Là câu lệnh. Lệnh này được gọi là lệnh while.

Thời gian thực hiện lệnh while được đánh giá : Giả sử thời gian thực hiện lệnh S (thân của lệnh while)  là O(f(n)). Giả sử g(n) là số tối đa các lần thực hiện  lệnh S , khi thực hiện lệnh while .Khi đó thời gian thực hiện lệnh while là O(f(n)g(n)).

Nếu S₁, S₂,....., Sn là các câu lệnh , E là biểu thức logíc thì

      Repeat S₁, S₂, .., Sn   until    E

      Là câu lệnh .Lệnh này được gọi là lệnh repeat.

Giả sử , thời gian thực hiện khối begin S₁, S₂,…Sn  end; là O(f(n)). Giả sử g(n) là số tối đa các lần lặp. Khi đó thời gian thực hiện lệnh repeat là O(f(n),g(n)).

Với S là câu lệnh và E₁,E₂ là biểu thức cùng một kiểu thứ tự đếm được thì

      For i:= E₁ to E₂  do  S     là câu lệnh ,và

      for i:= E₂ downto E₁ do S     là câu lệnh.

      Các câu lệnh này được gọi là lệnh for .

Thời gian thực hiện lệnh for được đánh giá tương tự như thời gian thực hiện lệnh while và lệnh repeat.

8. Đánh giá thủ tục (hoặc hàm) đệ qui.

Ví dụ: Đánh giá thời gian thực hiện của hàm đệ qui sau:

(hàm tính n!)

Function    fact(n:integer):integer;

Begin

      If n<=1 then fact :=1

            Else fact:=n*fact(n-1);

End;

Trong hàm này cỡ của dữ liệu vào là n. Giả sử thời gian thực hiện hàm là T(n) .Với n=1 chỉ cần thực hiện lệnh gán fact:=1; do đó T(1)= O(1). Với n>1 ,cần thực hiện lệnh gán fact:=n*(fact(n-1)). Do đó , thời gian T(n) sẽ là O(1) để thực hiện phép nhân (*) và phép gán(:=) cộng với thời gian T(n-1) để thực hiện lời gọi đệ qui fact(n-1). Tóm lại ta có quan hệ đệ qui như sau:

T(1) = O(1);

T(n) = O(1) + T(n-1);

Thay các O(1) bởi các hằng nào đó ta có quan hệ đệ qui như sau:

T(1) = C₁ ;

T(n) = C₂ + T(n-1);

Để giải phương trình đệ qui, tìm T(n), chúng ta áp dụng phương pháp thế lặp. Ta có phương trình đệ qui sau:

T(m) = C₂ + T(m-1); với m >1

Thay m lần lượt bởi các 2, 3,..,n-1,n ta được hệ các quan hệ sau:

T(2)    = C₂ + T(1);

T(3)    = C₂ + T(2);

................................

T(n-1) = C₂ + T(n-2);

T(n)    = C₂  + (n-1) ;

Bằng các phép thế liên tiếp ta nhận được

T(n) = (n-1).C₂ + T(1)

Hay   T(n) = (n-1) C₂  + C₁;, trong đó C₁, C₂ là các hằng nào đó .

Do đó T(n) = O(n) ;

            Từ đó ta có phương pháp tổng quát sau đây để đánh giá thời gian thực hiện các thủ tục (hàm)  đệ qui. Ta giả thiết rằng các thủ tục (hàm )là đệ qui trực tiếp. Điều đó có nghĩa là các thủ tục (hàm ) chỉ chứa các lời gọi đẹ qui đến chính nó (không qua một thủ tục hoặc hàm nào khác cả) . Giả sử thời gian thực hiện thủ tục (hàm ) là T(n), với n là cỡ dữ liệu vào .Khi đó thời gian thực hiện các lời gọi đệ qui thủ

tục sẽ là T(m) , với m<n .Đánh giá thời gian T(no) với n₀ là cỡ dữ liệu vào nhỏ nhất có thể được (trong ví dụ trên đó là T(1)). Sau đó đánh giá thân của thủ tục theo các qui tắc đã nêu trên ,ta sẽ nhận được quan hệ đệ qui như sau:

      T(n) = F(T(m₁),T(m₂),….,T(mk))

Trong đó m₁, m₂, ..... , mk < n. Giải phương trình đệ qui này ta sẽ nhận được sự đánh giá của T(n).

Bây giờ ta sử dụng những kiến thức trên để đánh giá hai ví dụ quen thuộc sau đây:

Ví dụ. Xác định độ phức tạp thuật toán của hàm tính  dãy số Fibonaci:

Function Fibo (n : integer) : integer;

Var i , j , k : integer ;

Begin

i := 1;

j := 0 ;

for k := 1 to  n do

Begin

      j := i + j ;

      i := j – i ;

End;

Fibo := j;

End;

Thời gian thực hiện của lệnh trên là O(n) .

Một bài toán thường có nhiều cách giải, hay nhiều thuật toán để giải, với mỗi thuật toán khác nhau có thể sẽ có độ phức tạp khác nhau. Đánh giá độ phức tạp thuật toán là một trong những cách phân tích, so sánh và tìm ra trong những thuật toán đó một thuật toán tối ưu.

Ví dụ.  Xét bài toán : Tính giá trị đa thức :

                                    P(x) = anxn + an_-1xn^-1 + ...... + a₁x + a₀ , với x = x₀

      Xét thuật toán 1 : 

            Tính giá trị từng hạng tử của đa thức :

1. Với i = 1 đến n tính aix₀ⁱ .
2. Tính 

            Đa thức P(x) có thể viết dưới dạng :

                        P(x) = (...((anx + an_-1)x...)x + a₀.

      Xét Thuật toán 2:

1. P := an .
2. Với i=1 đến n :  P := Px₀ + an_-i
3. Gán kết quả P(x₀)= P.

            Chẳng hạn với  n = 3.

                        P(x) = a₃x³ + a₂x² + a₁x + a₀ = (((a₃x + a₂)x +a₁) +a₀)

1. Tính P := a₃
2. i = 1 : P = (a₃x₀ + a₂)

            i = 2 : P = (a₃x₀ + a₂)x + a₁

            i = 3 : P = ((a₃x₀ + a₂)x + a₁)x + a₀

3. P(x₀) = ((a₃x₀+ a₂)x + a₁)x + a₀

      Xét độ phức tạp của hai thuật toán trên :

Thuật toán 1:  ở bước 1 ta có :

            i = 1 : ta phải thực hiện 1 phép nhân.

            i = 2 : ta phải thực hiện 2 phép nhân.

            ...............................................................

            i = n : ta phải thực hiện n phép nhân.

Như vậy  ở bước 1 ta sẽ phải thực hiện 1 + 2 + ….. + n =            

      ở bước 2 ta có :    ta phải thực hiện n phép cộng.

      Vậy ở thuật toán 1 cần   + n = 

Thuật toán 2: ta phải thực hiện n lần mỗi lần đòi hỏi 2 phép tính(một phép tính cộng và một phép tính nhân). Như vậy thuật toán 2 cần tất cả 2n phép tính.  Nếu ta coi thời gian thực hiện mỗi phép tính nhân và tính cộng là như nhau và là một đơn vị thời gian thì thời gian thực hiện thuật toán 1 là , còn thời gian thực hiện thuật toán 2 là 2n .

      Như vậy theo phân tích ở trên ta thấy rằng thời gian thực hiện thuật toán 2 ít hơn so với thời gian thực hiện thuật toán một. Thuật toán 2 có độ phức tạp là Q (n), độ phức tạp tuyến tính, còn thuật toán 1 thì độ phức tạp là Q(n²) độ phức tạp bậc hai.

Ta nhận thấy rằng việc đánh giá độ phức tạp của một thuật toán nào đó là việc không hề đơn giản nó đòi hỏi phải có phương pháp và cách tiếp cận riêng.

Ví dụ. Phân tích thuật toán Euclide tìm ước số chung lớn nhất của hai số nguyên dương a, b.

Thuật toán Euclide :

      Input    :  a, b là hai số nguyên dương.

      Output :  ước số chung lớn nhất của hai số a, b.

                  Function USCLN(a, b)

      Begin

                  x := a;

                  y := b;

      While y ¹ 0

                              begin

                                          r := x  mod  y            

                                          x := y;

                                          y := r;

                              end;

                  USCLN := x;

      End;    

Để đánh giá độ phức tạp của thuật toán trên, ta đếm số phép chia thực hiện theo thuật toán.

Ta chứng minh bằng qui nạp mênh đề sau :

      Mệnh đề 1 : Giả sử cặp số a, b,  a > b, đòi hỏi n ³ 1 phép chia trong thuật toán Euclde. Khi đó  a ³ fn₊₁  ,  b ³ fn  , trong đó dãy { fn }là dãy số Fibonaci  ( xác định bởi công thức truy hồi  fn₊₂ = fn + fn₊₁ , n ³ 2,  1=f₀ = f₁ và có công thức tường minh là        fn =).

      Chứng minh:  Dễ dàng kiểm tra mệnh đề đúng với n = 1. Giả sử mệnh đề đúng với n ³ 1. Ta chứng minh mệnh đề đúng với n+1. Giả sử cặp a, b, a>b đòi hỏi n+1 phép chia. Sau khi thực hiện phép chia a cho b :

                        a = bq + r,     0 £ r < b.

thuật toán tiếp tục làm việc với cặp số b, r ,  b > r. Cặp số này đòi hỏi n phép chia. Do đó theo giả thiết quy nạp :     b ³ fn₊₁  ,  r ³ fn . Từ đó suy ra

      a = bq + r ³  b + r ³  fn₊₁ + fn  = fn₊₂  .  Tức là ta có a ³ fn₊₂  , b ³ fn₊₁

Theo quy nạp  mệnh đề được chứng minh.

      Sử dụng mệnh đề trên ta có thể đánh giá được số phép chia nhiều nhất cần phải thực hiện trong thuật toán Euclide.

      Mệnh đề 2 : Đặt m=max{a,b} và giả sử thỏa mãn m ³ 8. Khi đó thuật toán đòi hỏi không quá log_3/2 (2m/3) phép chia

      Chứng minh : Thật vậy giả sử n là số phép chia lớn nhất cần thực hiện theo thuật toán với đầu vào thoả mãn điều kiện đặt ra trong mệnh đề. Giả sử cặp số a, b, m ³ a > b, đòi hỏi n phép chia. Do m ³ 8 nên bằng cách thử trực tiếp các khả năng có thể kiểm tra được là n ³ 4. Theo khẳng định của mệnh đề 1, ta có  a ³ fn₊₁ . Suy ra  fn₊₁ £  m. Do n +1 ³  5, nên có thể áp dụng công thức tường minh của dãy Fibonaci để chứng minh được là  (3/2)ⁿ⁺¹ < fn₊₁ Þ (3/2)ⁿ⁺¹ < m.   Hay ta có  n+1 < log_{3 / 2} m.

Suy ra :  n < log_3/2 m-1  = log_3/2 m - log_3/23/2  = log_3/2 (2m/3).

Mệnh đề được chứng minh.

Vậy độ phức tạp của thuật toán Euclide là O(log_3/2 (2m/3)), nó cũng là O(log(max{a,b})).

Nói chung, phân tích độ phức tạp thuật toán là một vấn đề phức tạp, nó đòi hỏi tư duy sáng tạo và có phương pháp với một cách tiếp cận riêng. Trong nhiều trường hợp ta không thu được kết quả đẹp như các ví dụ đã đưa ra.

Bài tập

1. Đánh giá độ phức tạp của các thuật toán của bạn:
2. a) Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn số thực.
3. b) Thuật toán tìm phần tử bé nhất của một tập con của tập hợp.
4. c) Thuật toán xếp lại một dãy theo thứ tự tăng dần.
5. d) Thuật toán tìm một dãy các số liên tiếp nhau (dài nhất có thể) có tổng dương trong một dãy số thực cho trước.

Xét lại vấn đề nhân các số nguyên lớn. Nhớ lại rằng thuật toán cổ điển mà phần lớn chúng ta đều được học ở trường đòi hỏi thời gian tính là Q(n²) để nhân các số nguyên có n chữ số. Chúng ta cũng quen với thuật toán này đến mức có thể còn chẳng bao giờ thắc mắc về tính tối ưu của nó. Liệu chúng ta có thể làm được tốt hơn không? . Một thuật toán được bàn đến gọi là kỹ thuật Chia để trị bao gồm việc rút gọn phép nhân hai số nguyên n chữ số xuống thành bốn phép nhân hai số nguyên n/2 chữ số.  Ví dụ

-         Việc nhân 2 số nguyên có 1 chữ số có thể thực hiện một cách trực tiếp (neo đệ qui), thời gian thực hiện là O(1)

-         Chia : n > 1 thì tích của hai số nguyên có n chữ số có thể biểu diễn qua tích 4 số nguyên có n/2 chữ số, thời gian thực hiện là 4.T(n/2) ( trong đó T(n)  là thời gian thực hiện nhân hai số nguyên có n chữ số ).

-         Tổng hợp : Cộng và dịch phải, khi đó thời gian thực hiện sẽ là O(n)

Khi đó ta có thời gian thực hiện thuật toán là

Theo định lý thợ ta có độ phức tạp của thuật toán là  .Như vậy thuật toán thu được cũng không gặt hái được bất kỳ cải thiện nào so với thuật toán nhân cổ điển mặc dù chúng ta đã khôn ngoan hơn. Để vượt được thuật toán cổ điển và như vậy mới hoàn toàn thấy rõ được công dụng của phép Chia để trị, chúng ta phải tìm cách rút gọn phép nhân nguyên thuỷ không phải về bốn mà là ba phép nhân hai nửa.

      Chúng ta minh hoạ quá trình này bằng việc nhân 981 với 1234. Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn một số không vô nghĩa để làm cho hai toán hạng có cùng độ dài, vậy là 981 trở thành 0981. Sau đó tách từng toán hạng thành hai nửa: 0981 cho ra w = 09 và x = 81, còn 1234 thành y = 12 và z = 34. Lưu ý rằng 981 = 10²w + x và 1234 = 10²y + z. Do đó, tích cần tìm có thể tính được là

      981 x 1234 = (10²w + x)( 10²y + z)

                         = 10⁴wy + 10²(wz + xy) + xz

                         = 1080000 + 127800 + 2754 = 1210554

      Thủ tục trên đến bốn phép nhân hai nửa: wy, wz, xy và xz.

            Để ý điểm mấu chốt ở đây là thực ra thì không cần tính cả wz lẫn xy, mà là tổng của hai số hạng này. Liệu có thể thu được wz + xy với chi phí của một phép nhân mà thôi hay không? Điều này có vẻ như không thể được cho đến khi chúng ta nhớ ra rằng mình cũng cần những giá trị wy và xz để đưa vào công thức trên. Lưu ý về điểm này, hãy xét tích:

                        r = (w + x)(y+z) = wy + (wz + xy) + xz

      Chỉ sau một phép nhân, chúng ta thu được tổng của tất cả ba số hạng cần thiết để tính được tích mình mong muốn. Điều này gợi ý một cách tiến hành như sau:

                        p = wy = 09 * 12 = 108

                        q = xz = 81 * 34 = 2754

                        r = (w + x)(y+z) = 90 * 46 = 4140

      và cuối cùng

                        981 x 1234 = 10⁴p + 10²(r – p – q) + q

                                          = 1080000 + 127800 + 2754 = 1210554.

      Như vậy tích của 981 và 1234 có thể rút gọn về ba phép nhân của hai số có hai chữ số (09  12, 81  34 và 90  46) cùng với một số nào đó phép dịch chuyển (nhân với luỹ thừa của 10), phép cộng và phép trừ.

      Chắc chắn là số các phép cộng – coi phép trừ như là phép cộng – có nhiều hơn so với thuật toán Chia để trị nguyên thuỷ ở phần trước. Vậy thì có đáng để thực hiện bốn phép cộng nhiều hơn để tiết kiệm một phép nhân hay không? Câu trả lời là không nếu chúng ta đang nhân số nhỏ như những số trong ví dụ này. Tuy nhiên sẽ là đáng giá nếu các số cần được nhân với nhau đủ lớn và chúng càng lớn thì lại càng đáng làm như vậy. Khi các số hạng đủ lớn, thời gian cần cho các phép cộng và dịch chuyển trở thành bỏ qua được so với thời gian cần cho chỉ một phép nhân. Như vậy là có lý do để kỳ vọng rằng rút gọn bốn phép nhân về còn ba sẽ giúp chúng ta cắt giảm được 25% thời gian tính toán đòi hỏi cho việc nhân các số lớn. Như chúng ta sẽ thấy, sự tiết kiệm của mình sẽ tốt hơn một cách đáng kể.

            Để giúp chúng ta hiểu thấu được những gì mình đạt được, hãy giả thiết rằng có một cài đặt của thuật toán nhân cổ điển đòi hỏi thời gian h(n) =  cn² để nhân hai số có n chữ số, với hằng số c phụ thuộc vào cài đặt đó. (ở đây đã có sự đơn giản hoá vì trên thực tế thì thời gian đòi hỏi còn có dạng phức tạp hơn, chẳng hạn như cn² + bn + a). Tương tự, cho g(n) là thời gian mà thuật toán Chia để trị cần để nhân hai số n chữ số, không tính thời gian cần thiết để thực hiện ba phép nhân hai nửa. Nói cách khác, g(n) là thời gian cần thiết cho các phép cộng, dịch chuyển và các phép tính phụ thêm khác. Dễ dàng cài đặt các phép tính này sao cho g(n) Î Q(n). Hãy tạm thời bỏ qua điều gì sẽ xảy ra nếu n lẻ và nếu các số hạng không có cùng độ dài.

      Nếu từng trong số ba phép nhân hai nửa được thực hiện bằng thuật toán cổ điển, thời gian cần thiết để nhân hai số có n chữ số là:

                        3h(n/2) + g(n) = 3c(n/2)² + g(n) =  cn² + g(n)=  h(n) + g(n).

      Vì h(n) Î Q(n²) và g(n) Î Q(n), số hạng g(n) là bỏ qua được so với  h(n) khi n đủ lớn, có nghĩa là chúng ta tăng được tốc độ lên khoảng 25% so với thuật toán cổ điển như đã mong đợi. Mặc dù sự cải thiện này là không thể xem thường được nhưng chúng ta vẫn không làm được thay đổi bậc của thời gian cần thiết: thuật toán mới vẫn cần thời gian tính bậc hai.

      Để có thể làm được tốt hơn thế, chúng ta trở lại với câu hỏi đặt ra ở đoạn mở đầu: các bài toán con cần được giải như thế nao? Nếu chúng nhỏ thôi thì thuật toán cổ điển có thể vẫn còn là cách làm tốt nhất. Tuy nhiên, khi những bài toán con cũng đủ lớn, chẳng lẽ sử dụng thuật toán mới của chúng ta một cách đệ quy cũng không hơn gì hay sao? ý tưởng này tương tự như hưởng lợi nhuận từ một tài khoản ngân hàng có gộp vốn lẫn lãi! Nếu chúng ta làm như vậy sẽ thu được một thuật toán có thể nhân hai số n chữ số trong một thời gian t(n) =  3t(n/2) + g(n) khi n chẵn và đủ lớn. Điều này cũng giống như phép truy toán (đệ quy) ; giải ra ta thu được t(n) Î O(nlg³) | n là luỹ thừa của 2. Chúng ta cần phải bằng lòng với lời ghi chú tiệm cận có điều kiện vì chưa đề cập đến câu hỏi là nhân các số có độ dài là lẻ như thế nào.

      Vì lg3 = 1.585 nhỏ hơn 2, thuật toán này có thể nhân hai số nguyên lớn nhanh hơn rất nhiều so với thuật toán nhân cổ điển và n càng lớn thì sự cải thiện này càng đáng giá. Một cài đặt tốt có thể không sử dụng cơ số 10, mà sử dụng cơ số lớn nhất để với cơ số đó phần cứng cho phép nhân trực tiếp hai “chữ số” với nhau.

Một nhân tố quan trọng trong hiệu suất thực tế của cách tiếp cận phép nhân này và của bất kỳ thuật toán Chia để trị nào là biết khi nào cần dừng việc phân chia các bài toán và thay vào đó sử dụng thuật toán cổ điển. Mặc dù cách tiếp cận Chia để trị trở nên có ích khi bài toán cần giải đủ lớn, trên thực tế nó có thể chậm hơn so với thuật toán cổ điển đối với những bài toán quá nhỏ. Do đó thuật toán       Chia để trị phải tránh việc thực hiện đệ quy khi kích thước của các bài toán con không phù hợp nữa. Chúng ta sẽ trở lại vấn đề này ở phần sau.

      Để đơn giản, một số vấn đề quan trọng đến nay đã bị bỏ qua. Làm thế nào để chúng ta giải quyết được những số có độ dài lẻ? Mặc dù cả hai nửa của số nhân và số bị nhân đều có kích thước n/2, có thể xảy ra trường hợp tổng của chúng bị tràn và có kích thước vượt quá 1. Do đó sẽ không hoàn toàn chính xác khi nói rằng r = (w+x)(y+z) bao hàm phép nhân hai nửa. Điều này ảnh hưởng tới việc phân tích thời gian chạy như thế nào? Làm thế nào để nhân hai số có kích thước khác nhau? Còn những phép tính số học nào khác với phép nhân mà ta có thể xử lý hiệu quả hơn so với dùng thuật toán cổ điển?

      Những số có độ dài lẻ được nhân dễ dàng bằng cách tách chúng càng gần ở giữa càng tốt: một số có n chữ số được tách thành một số có |n/2| chữ số và một số có |n/2| chữ số. Câu hỏi thứ hai còn khắt khe hơn. Xét nhân 5678 với 6789. Thuật toán của chúng ta tách các số hạng thành w = 56, x = 78, y = 67 và z = 89. Ba phép nhân hai nửa cần thực hiện là:

                        p = wy = 56  67

                        q = xz = 78  89 và

                        r = (w+x)(y+z) = 134  156

      Phép nhân thứ ba bao gồm những số 3 chữ số, do vậy nó không thực sự là một nửa so với phép nhân nguyên thuỷ của các số có 4 chữ số. Tuy nhiên kích thước của w+x và y+z không thể vượt quá 1 + |n/2|.

      Để đơn giản hoá việc phân tích, cho t(n) là thời gian mà thuật toán này thực hiện trong tình huống xấu nhất để nhân hai số có kích thước tối đa là n (thay vì chính xác bằng n). Theo định nghĩa thì t(n) là một hàm không giảm.   Khi n đủ lớn thuật toán của chúng ta rút gọn phép nhân hai số có kích thước tối đa n đó về ba phép nhân nhỏ hơn p = wy, q = xz và r = (w+x)(y+z) với kích thước tối đa tương ứng là |n/2|, |n/2| và 1 + |n/2|, thêm vào đó là những thao tác đơn giản chiếm thời gian là O(n). Do đó ở đây tồn tại hằng số dương c sao cho:

                        t(n) = t(|n/2|) + t(|n/2|) + t(1+|n/2|) + cn

với mọi n đủ lớn. Điều này chính xác là phép đệ quy mà chúng ta đã nghiên cứu cho kết quả giờ đây đã trở nên quen thuộc là t(n) Î O(nlg³). Do vậy luôn luôn có thể nhân các số n chữ số với thời gian O(nlg³). Phân tích tình huống tồi nhất của thuật toán này chỉ ra rằng trên thực tế t(n) Î Q(nlg³), nhưng điều này không được quan tâm lắm vì còn có những thuật toán nhân nhanh hơn.

      Quay lại với câu hỏi nhân các số có kích thước khác nhau, giả sử u và v là những số nguyên có kích thước tương ứng là m và n. Nếu m và n nằm trong khoảng đến hai lần của nhau, tốt nhất là điền vào số hạng nhỏ hơn những số 0 vô nghĩa để làm cho nó có cùng độ dài như số hạng kia, như chúng ta đã làm khi nhân 981 với 1234. Tuy nhiên cách tiếp cận này không được khuyến khích khi một số hạng lớn hơn số hạng kia rất nhiều. Thậm chí  nó có thể tồi hơn là dùng thuật toán nhân cổ điển! Không làm mất đi tính tổng quát, giả sử rằng m ³ n. Thuật toán Chia để trị sử dụng điền số và thuật toán cổ điển có thời gian tương ứng là Q(nlg³) và Q(mn) để tính các tích u và v. Xét thấy rằng hằng số ẩn của biểu thức trước có vẻ lớn hơn của biểu thức sau, chúng ta thấy rằng Chia để trị sử dụng điền số là chậm hơn thuật toán cổ điển khi m = nlg^(3/2) và như vậy trường hợp đặc biệt khi m = n.

            Mặc dù vậy rất dễ dàng kết hợp cả hai thuật toán để thu được một thuật toán thực sự tốt hơn. ý tưởng là cắt lát số hạng dài hơn v thành những đoạn có kích thước m và sử dụng thuật toán Chia để trị để nhân u với từng đoạn của v sao cho thuật toán Chia để trị được dùng để nhân những cặp số hạng có cùng kích thước. Tích cuối cùng của u và v sau đó thu được dễ dàng bằng các phép cộng và dịch chuyển đơn giản. Thời gian chạy tổng cộng chủ yếu được dùng để thực hiện |n/m| phép nhân các số m chữ số. Vì mỗi phép nhân nhỏ hơn này chiếm thời gian Q(mlg³) và vì |n/m| Î Q(n/m), thời gian chạy tổng cộng để nhân một số n chữ số với một số m chữ số là Q(nmlg^(3/2)) khi m = n.

Sau đây là mô hình cải tiến thuật toán nhân số nguyên lớn

Cải tiến để còn lại 3 phép nhân :

Từ đó ta đưa ra thuật toán nhân số nguyên lớn là

Function  Karatsuba(x,y,n);

      Begin

            If n = 1 then   Return   x[0]*y[0]

            Else

                        Begin

                                    a := x[n-1]. . . x[n/2];         b := x[n/2-1] . . . x[0];

                                    c := y[n-1]. . . y[n/2];          d := y[n/2-1] . . . y[0];

                                    U := Karatsuba(a,c,n/2);

                                    V := Karasuba(b,d,n/2);

                                    W := Karatsuba(a+b,c+d,n/2);

                                    Return    U*10ⁿ + (W-U-V)*10^n/2 + V

                        end

      End;

Phân tích hiệu quả thuật toán : T(n)

                        T(1) = 1

                        T(n) = 3 T(n/2) + cn

=> Theo định lý thợ    T(n) = Q(nlog ³)