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 toán ứng tuyển của một bài toán, ta có thể dễ dàng nhận ra thuật toán nào là hiệu quả nhất. Kiểu phân tích như vậy có thể nêu rõ nhiều ứng viên tồn tại, song một vài thuật toán kém hơn thường bị loại trong khi tiến hành.
Để có thể phân tích một thuật toán, ta phải áp dụng một mô hình
công nghệ thực thi, kể cả mô hình cho các tài nguyên của công nghệ đó và các chi phí của chúng, Đa phần tập sách này mặc nhận sử dụng mô hình điện toán RAM (random-access machine= máy truy cập ngẫu nhiên), một bộ xử lý chung, làm công nghệ thực thi và ngầm hiểu rằng các thuật toán sẽ được thực thi dưới dạng các chương trình máy tính. Trong mô hình RAM, các chỉ lệnh được thi hành lần lượt, mà không có các phép toán đồng thời. Tuy nhiên, trong các chương sau, ta sẽ có dịp nghiên cứu các mô hình của các máy tính song song và phần cứng số hóa.
Quá trình phân tích luôn là một thách thức, thậm chí với một thuật toán đơn giản. Các công cụ toán học cần thiết có thể gồm cả toán học tổ hợp trừu tượng, lý thuyết xác suất căn bản, kỹ năng về đại sô”, và khả năng định danh các số hạng quan trọng nhất trong một công thức. Do cách ứng xử của một thuật toán có thể khác nhau đối với từng đầu vào khả dĩ, nên ta cần có một biện pháp để tóm lược cách ứng xử thành các công thức đơn giản và dễ hiểu.
Cho dù thông thường chỉỉựa mô hình một máy để phân tích một thuật toán nào đó, song ta vẫn phải đốì mặt với nhiều chọn lựa khi quyết định cách diễn tả tiến trình phân tích. Một mục tiêu tức thời đó là tìm một biện pháp diễn tả đơn giản để viết và điều tác [manipulate], nêu các đặc tinh quan trọng của các yêu cầu tài nguyên của một thuật toán, và hủy bỏ các chi tiết dài dòng.
Phân tích kỹ thuật sắp xếp chèn
Thời gian kéo dài của thủ tục INSERTION-SORT thường tùy thuộc vào đầu vào: tiến trình sắp xếp một ngàn con số sẽ lâu hơn tiến trình sắp xêp ba con sô”. Vả lại, INSERTION-SORT có thể sửdụng các thời lượng khác nhau để sắp xếp hai dãy đầu vào có kích cỡ giống nhau, tùy thuộc vào mức độ sắp xếp sấn của chúng. Nói chung, thời gian thực hiện của một thuật toán thường tăng theo kích cỡ đầu vào, do đố theo truyền thông, ta thường mô tả thời gian thực hiện của một chương trình như một hàm kích cỡ đầu vào của chương trình đổ. Để thực hiện, ta cần định nghĩa các thuật ngữ “thời gian thực hiện” [running time] và “kích cỡ đầu vào” [size of input] cẩn thận hơn.
Ý niệm thích hợp nhâl của kích cỡ đầu vàothường tùy thuộc vào bài toán đang nghiên cứu. Với nhiều bài toán, như sắp xếp hoặc tính toán các phép biến đổi Fourier, số đo tự nhiên nhất đó là số lượng các mục
trong đầu vào—ví dụ, kích cỡ mảng n để sắp xếp. Với nhiều bài toán khác, như nhân hai sô” nguyên, sô” đo tô”t nhất của kích cỡ đầu vào lại là tổng sốbitcần thiết để biểu thị đầu vào theo hệ ký hiệu nhị phân bình thường. Đôi lúc, việc mô tả kích cỡ đầu vào bằng hai con sô” thay vì một lại tỏ ra thích hợp hơn. Ví dụ, nếu đầu vào cho một thuật toán là một đồ thị, kích cỡ đầu vào có thể được mô tả bởi các sô” đỉnh [vertices] và các cạnh trong đồ thị. Ta sẽ nêu rõ kiểu đo kích cỡ đầu vào sẽ được dùng với từng bài toán mà ta nghiên cứu.
Thời gian thực hiện[running time] của một thuật toán trên một đầu vào cụ thể chính là sô” lượng phép toan nguyên tô” [primitive operations] hoặc “các bước” [steps] được thi hành. Sẽ tiện dụng hơn nếu ta định nghĩa khái niệm “bước” để nó càng độc lập máy càng tốt. Trước mắt, hãy chấp nhận quan điểm sau. cần có một thời lượng bâ”t biến để thi hành từng dòng mã giả của chúng ta. Dòng này có thểmâ”t một thời lượng khác với dòng kia, song ta mặc nhận rằng từng đợt thi hành dòng thứì sẽmâ”t một thời gian c, ở đó c là một hằng. Quan điểm này phù hợp với mô hình RAM, và nó cũng phản ánh cách thực thi mã giả trến hầu hết các máy tính hiện nay .
Trong đoạn mô tả dưới đây, cách diễn tả của chúng ta về thời gian thực hiện của INSERTION-SORT sẽ tiến hóa từ một công thức hỗn độn sử dụng tất cả mọi hao phí câu lệnh c. thành một hệ ký hiệu đơn giản hơn nhiều, dễ dàng điều tác và súc tích hơn. Hệ ký hiệu đơn giản này cũng sẽ giúp ta dễ dàng xác định xem thuật toán này có hiệu quả hơn thuật toán kia hay không.
Để bắt đầu, ta trình bày thủ tục INSERTION-SORT bằng các mức “hao phí” thời gian của từng câu lệnh và sô” lần thi hành từng câu lệnh. Với mỗi j = 2,3ở đó n = \ength[A\ ta giả sửt, là sô” lần thi hành đợt trắc nghiệm vòng lặp while trong dòng 5 theo giá trịj đó. Ta mặc nhận rằng các chú giải không phải là các câu lệnh thi hành, và do đó không mất thời gian.
Thời gian thực hiện của thuật toán là tổng các thời gian thực hiện của từng câu lệnh được thi hành; một câu lệnh trải qua các bước c để thi hành và được thi hành n lần sẽ đóng góp cn vào tổng thời gian thực hiện3. Để tính T{n\ thời gian thực hiện của INSERTION-SORT, ta tổng cộng các tích của các cột costsvà times, thành
T(n) = c n + c (n – l)+c (n -1)+ c £/ + ci (t – I)+ c Ế(t-1)+ c (n-\)
12 4 5 7=2J b 7=2 7=2 J 8
Thậm chí với các đầu vào có một kích cỡ nhất định, thời gian thực hiện của một thuật toán có thể tùy thuộc vào việc cho đầu vào nào có kích cỡ đó. Ví dụ, trong INSERTION-SORT, trường hợp tốt nhất xảy ra khi mảng đã được sắp xếp sấn. Với mỗi j = 2, 3, …, n, ta thấy rằng A[i] <keytrong dòng 5 khi i có giá trị ban đầu là j – 1. Như vậy t = 1 với j = 2, 3,…, n, và thời gian thực hiện trong trường hợp tốt nhất là:
T(n) = c{n + c2(n – 1) + cẶn – 1) + c5(n – 1) + cẶn – 1)
= (c, + c2 + c4 + c5 + cs)« – (c2 + c4 + c5 + c8>-
Thời gian thực hiện này có thể được diễn tả là: an + b với các hằng a và by tùy thuộc vào hao phí câu lệnh c; do đó nó là một hàm tuyến tính của n.
Nếu mảng được sắp xếp theo thứ tự đảo ngược—nghĩa là, theo thứ tự giảm—trường hợp xấu nhất sẽ xảy ra. Ta phải so sánh mỗi thành phần A[j] với mỗi thành phần trong nguyên cả mảng con đã sắp xếp A[\.j – 1 ], và như vậy t. = j với j = 2, 3 n. Lưu ý rằng
và
ÍO-l,= ĩ^
>2 2
(Chương 3 sẽ đề cập lại các phép tổng này), ta thấy rằng trong trường hợp xấu nhất, thời gian thực hiện của INSERTION-SORT là
T(n) = c,n+ c2ịn-1) + ct(n-1) + c5 – l)
+ c, + c, (“í|íl- l)+ c,(«-l)
ịiỵ + Ỵ + lỵjn +ịc, + c, + c4 + Ẹ* + Ẹịị + ị + Cxj n
* (c2 + c4 + c5 + c8)
Thời gian thực hiện trường hợp xấu nhất này có thể được diễn tả là an2+ bn + c với các hằng at bt và c, mà một lần nữa tùy thuộc vào hao phí câu lệnh c.; do đó nó là một hàm bậc hai của n.
Thông thường, như trong trường hợp sấp xếp chèn, thời gian thực hiện của một thuật toán được cô” định theo một đầu vào đã cho, mặc dù trong các chương sau, ta sẽ gặp các thuật toán “ngẫu nhiên hóa” [ran¬domized] đáng quan tâm có cách ứng xử có thể thay đổi thậm chí với cả đầu vào cố định.
