Chương 1 Giới thiệu 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 đướ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ó đị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ỉ lự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 đố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 tính 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 chỉ tiết đà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ất của kích cỡ đầu vào thườn g 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 12 Phân tích Các Thuật toán 25 trong đầu vào—ví dụ, kích cỡ mắng n dé 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ố bit cầ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] cua một thuật toán trên một đầu vào cụ thể chính là số lượng phép toán 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 thir i 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.,n, ở đó n = length[A], ta giả sử 1 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. 3 Ở đây có vài điểm tỉnh tế. Các bước tính toán mà ta đặc tả bằng tiếng Anh thường là các biến thể của một thủ tục yêu cầu không chỉ một thời lượng bất biến. Ví dụ, ở phần sau trong cuốn sách này, ta có thể nói “sort the points by x-coordinate” [sắp xếp các điểm theo tọa độ x].
mà như sẽ thấy. sẽ vận dụng nhiễu hơn một thời lượng bất biến. Ngoài ra cũng lưu ý, một câu lệnh gọi một chương trình con sẽ mất một thời lượng bất biến. tuy rằng raột khi được triệu gọi, chương trình con có thể mất nhiều thời gian hơn.
Nghĩa là, ta tách riêng tiến trình gọi chương trình con—chuyền các tham số cho nó, vân vân—với tiến trình /fi hành chương trình con đổ. - 26 Chương 1 Giới thiệu INSERTION-SORT(4) costs times | for j < 2 to length [A] €, n 2 do key — A[ ] cone 3 [> chén A[j] vào chuỗi có sắp xếp > sequence A[l.0 n—Ì 4 ¡ cj -] c, one 5 while i > 0 and A[i ] > key ¢, Dee 6 do A [iti]<—Ali] C5 Dt D 7 ici-l —. 8 Ali+ l] © key Cy n— ÌÏ 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 ø lần sẽ đóng góp cø vào tổng thời gian thực hiện. Để tính 7(n), thời gian thực hién cla INSERTION-SORT, ta tổng cộng các tích của các cột cosis và (mes, thành T(n) = cn + cn 1)+e(n -1)+ ¢, dnt Ẳ DU 1+ c, 2 (t-1)+ c, (n-1) 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., n, ta thấy rằng A[ï] < key trong dòng 5 khi ¿ có giá trị ban đầu là j - I. Như vậy i= lvdij= 2, 3,. n, và thời gian thực hiện trong trường hợp tốt nhất là: Tím) = cạn + cjÚn - |) + cứn - |) + c(n + |) + cứn = 1) =(c, +c, +c,+0¢,+¢,)n-(c,+¢, +, + C,). Thời gian thực hiện này có thể được diễn tả là: an + b với các hằng ø và b, 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[7] với mỗi thành phần trong nguyên cả mắng con đã sắp xếp A[I./ — 1], và như vậy ¡ = j vớij = 2, 3,. - -_ Đặc tính này không nhất thiết áp dụng cho một tài nguyên như bộ nhớ. Một câu lệnh tham chiếu m tt [words] của bộ nhớ và được thi hành ø lần không nhất thiết tiêu thụ tổng cong mn ti cla bd nhớ.2 Phân tích Các Thuật rn.
H(n +Ì) >J” 1 j=2 2 và Šú-UD= ne. ) - (65, % ) ( to¢q s) Dwele Co Ce € + at St st (5 fs Sy 22 tt tt 42176770 - (C; + c¿ + €; + Œ) diễn tả là Thời gian thực hiện trường hợp xấu nhất này có thể được lần nữa tùy thuộc vào hao an? + bn + c với các hing a, b, và c, mà một của n. phí câu lệnh c„ do đó nó là một hàm bậc hai thời gian thực Thông thường, như trong trường hợp sắp xếp chèn, vào đã cho, mặc dù hiện của một thuật toán được cố định theo một đầu “ngẫu nhiên hóa” [ran- trong các chương sau, ta sẽ gặp các thuật toán thậm chí với cả domized] đáng quan tâm có cách ứng xử có thể thay đối đầu vào cố định. g bình Phân tích trường hợp xấu nhất và trường hợp trun xem xét cả ca Trong kỹ thuật phân tích sắp xếp chèn trên đây, ta đã lẫn trường hợp xấu tốt nhất, ở đó mắng đầu vào đã được sắp xếp sẵn, Tuy nhiên, với phần nhất, ở đó mảng đầu vào được sắp xếp đảo ngược.
việc chỉ tìm thời gian thực còn lại của cuốn sách, ta thường tập trung vào dài nhất của một hiện trường hợp xấu nhất; nghĩa2 là, thời gian thực hiện vì ba lý do khả đĩ sau đây. đầu vào bất kỳ có kích cỡ n. Sở dĩ như vậy là thuật toán là một e Thời gian thực hiện trường hợp xấu nhất của một của một đầu vào bất cận trên [upper bound] đối với thời gian thực hiện bao giờ kéo dài hơn nữa. Biết rằng nó bảo đảm thuật toán sẽ không thời gian thực hiện và hy vọng Ta không cần phải suy đoán này nọ về nó không trở nên tệ hại hơn.
khá thường xuyên. © Với vài thuật toán, trường hợp xấu nhất xảy ra sở dữ trong một cơ Ví dụ, trong khi tìm kiếm “ một mẩu thông tin cụ thể“ kiếm thường xảy ra khi liệu, trường hợp xấu nhất của thuật toán tìm 28 Chuong 1 Gidi thiéu thông tin đó không hiện diện trong cơ sở dữ liệu. Trong vài ứng dụng tìm kiếm, ta thường gặp các đợt tìm kiếm thông tin vắng mặt. Thông thường, “trường hợp trung bình” [average case] cũng tệ hại tương tự như trường hợp xấu nhất.
Giả sử, ta ngẫu nhiên chọn n con số và áp dụng kỹ thuật sắp xếp chèn. Phải mất bao lâu để xác định vị trí chèn thành phần A [7] trong mảng con A[I.,/ - 1]? Tính trung bình, phân nửa các thành phần trong A[I.,/ - !] là nhỏ hơn A [ÿ], và phân nửa các thành phần là lớn hơn. Như vậy, tính trung bình, ta kiểm tra phân nửa mang con A[I.,j - 1], do dé 1 =jf.