Thiết kế và đánh giá thuật toán

khối lệnh 2

.......

case nk khối lệnh k [ default

khối lệnh k+1]

}

Với ni là các số nguyên, hằng ký tự hoặc biểu thức hằng. Các ni cần có giá trị khác nhau. Đoạn chương trình nằm giữa các dấu { } gọi là thân của toán tử switch.

default là một thành phần không bắt buộc phải 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)

Lệnh hoặc khối lệnh;

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 có giá trị khác không (biểu thức đúng), máy sẽ thực hiện lệnh hoặc khối lệnh trong thân của while. Khi máy thực hiện xong khối lệnh này nó lại thực hiện xác định lại giá trị biểu thức rồi làm tiếp các bước như trên.

* 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)

Lệnh hoặc khối lệnh ;

Toán tử for gồm ba biểu thức và thân for. Thân for là một câu lệnh hoặc một khối lệnh viết sau từ khoá for. Bất kỳ biểu thức nào trong ba biểu thức trên có thể

vắng mặt nhưng phải giữ dấu ;

Thông thường biểu thức 1 là toán tử gán để tạo giá trị ban đầu cho biến điều khiển, biểu thức 2 là một quan hệ logic biểu thị điều kiện để tiếp tục chu trình, biểu thức ba là một toán tử gán dùng để thay đổi giá trị 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 : Xác định biểu thức 1

Xác định biểu thức 2

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.

* Cấu trúc do-while

Khác với các toán tử while và for, việc kiểm tra điều kiện kết thúc đặt ở đầu

chu trình, trong chu trình do while việc kiểm tra điều kiện kết thúc đặt cuối chu trình. Như vậy thân của chu trình bao giờ cũng đượ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.

Khi thực hiện xong tất cả các lệnh trong thân của chu trình, máy sẽ xác định giá trị của biểu thức sau từ khoá while rồi quyết định thực hiện như sau :

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

Câu lệnh break cho phép ra khỏi các chu trình với các toán tử for, while, do while và switch. Khi có nhiều chu trình lồng nhau, câu lệnh break sẽ đưa máy ra khỏi chu trình bên trong nhất chứa nó không cần điều kiện gì.

* Câu lệnh continue :

Trái với câu lệnh break, lệnh continue dùng để bắt đầu một vòng mới của

chu trình chứa nó. Trong while và do while, lệnh continue chuyển điều khiển về thực hiện ngay phần kiểm tra, còn trong for điều khiển được chuyển về bước khởi đầu lại (tức là bước : 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). Lệnh continue chỉ áp dụng cho chu trình chứ không áp dụng cho switch.

1.4. Thiết kế thuật toán

1.4.1. Modul hoá và thiết kế từ trên xuống

Các bài toán giải được trên máy tính ngày càng phức tạp và đa dạng. Các thuật toán giải chúng ngày càng có quy mô lớn đòi hỏi nhiều thời gian và công sức của nhiều người. Tuy nhiên công việc sẽ đơn giản hơn nếu như ta chia bài toán ra thành các bài toán nhỏ. Điều đó cũng có nghĩa là nếu coi bài toán là modul chính thì cần chia thành các modul con. Đến lượt mình các modul con lại phân rã thành các modul con thích hợp...

Như vậy việc tổ chức lời giải thể hiện theo một cấu trúc phân cấp. Chiến thuật giải bài toán như vậy là “chia để trị”, thể hiện chiến thuật đó ta

dùng thiết kế từ trên xuống. Đó là cách nhìn nhận vấn đề một cách tổng quát, đề cập đến các công việc chính, sau đó mới bổ sung dần các chi tiế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 sẽ thể hiện dần từ ngôn ngữ tự nhiên, sang ngôn ngữ mã giả rồi đến ngôn ngữ lập trình, và đi từ mức “làm cái gì“đến “làm như thế nào”.

1.4.3. Một số kỹ thuật thiết kế

Trên cơ sở lý thuyết máy Turing, người ta chia được các bài toán thành 2 lớp không giao nhau : Lớp giải được bằng thuật toán, và lớp không giải được bằng thuật toán.

Đối với lớp các bài toán giải được bằng thuật toán, dựa vào các đặc trưng của quá trình thiết kế của thuật toán, ta có thể chỉ ra một số các kỹ thuật thiết kế thuật toán cơ bản sau đây :

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 .

2) Kỹ thuật quay lui Tìm kiếm theo ưu tiên.

Đối với mỗi bước thuật toán, ưu tiên theo độ rộng hay chiều sâu để tìm kiếm.

Chẳng hạn thuật toán giải bài toán 8 hậu.

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 tìm kiếm lời giải, ta phân hoạch tập các phương án của bài toán ra thành hai hay nhiều tập con được biểu diễn như là các nút của cây tìm kiếm và cố gắng bằng phép đánh giá cận cho các nút, tìm cách loại bỏ các nhánh của cây mà ta biết chắc không chứa phương án tối ưu.

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 tổ chức tìm kiếm lời giải theo kiểu từ dưới lên. Xuất phát từ các

bài toán con nhỏ và đơn giản nhất, tổ hợp các lời giải của chúng để có lời giải của bài toán con lớn hơn...và cứ như thế cuối cùng được lời giải của bài toán ban đầu.

1.5. Phân tích thuËt toán

Trong khi giải một bài toán chúng ta có thể có một số thuật toán khác nhau, vấn đề là cần phải đánh giá các thuật toán đó để lựa chọn một thuật toán tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:

- Thuật toán đơn giản

- Thuật toán thực hiện nhanh

Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu thuật toán đơn giản là quan trọng. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết quả, thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi.

Tuy nhiên khi một chương trình được sử dụng nhiều lần thì yêu cầu tiết kiệm thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu thuật toán thực hiện nhanh sẽ được xem xét một cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của thuật toán. Hơn nữa khối lượng dữ liệu lớn mà dung lượng bộ nhớ lại có giới hạn thì không thể bỏ qua yêu cầu về tiết kiệm bộ nhớ được. Tuy nhiên cân đối giữa yêu cầu về thời gian và không gian không mấy khi có được một giải phấp trọn vẹn.

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 phương pháp để xác định 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 lường thời gian thực hiện của hoạt động trên một máy tính xác định đối với tập hợp được chọn lọc các dữ liệu vào.

Thời gian thực hiện không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào tập các chỉ thị của máy tính, chất lượng của máy tính và kĩ xảo của người lập trình. Sự thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ liệu vào được chọn. Ðể vượt qua các trở ngại này, các nhà khoa học máy tính đã chấp nhận tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự thực thi của thuật toán. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và đặc biệt đối với sự phức tạp thời gian trong trường hợp xấu nhất.

Nói chung thì thời gian thực hiện thuật toán không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng kích thước nhưng thời gian thực hiện giải thuật có thể khác nhau. Chẳng hạn chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một

dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một dãy đã có thứ tự giảm.

Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.

Để đánh giá thời gian thực hiện thuật toán người ta tìm cách đánh giá độc lập với các yếu tố bên ngoài như máy tính hay các yếu tố liên quan đến máy tính. Cách đánh giá như vậy dẫn tới khái niệm về cấp độ lớn của thời gian thực hiện thuật toán hay độ phức tạp tính toán của thuật toán.

1.5.2. Độ phức tạp tính toán của thuật toán

Nếu thời gian thực hiện một thuật toán là T(n) =cn2 (với c là hằng số, n là kích thước dữ liệu đầu vào) thì ta nói: Độ phức tạp tính toán của thuật toán này có cấp là n2 (hay cấp độ lớn của thời gian thực hiện thuật toán là n2) và ta ký hiệu:

T(n) = O(n2) (ký hiệu chữ O lớn) Một cách tổng quát có thể định nghĩa:

Một hàm f(n) được xác định là O(g(n)) và viết là f(n) =O(g(n)) và được gọi là cấp g(n) nếu tồn tại các hằng số c và n0 sao cho:

f(n) ≤ cg(n) khi n ≥ n0

nghĩa là f(n) bị chặn trên bởi một hằng số nhân với g(n), với mọi giá trị của n tăng từ một điểm nào đó. Thông thường các hàm thể hiện độ phức tạp tính toán của thuật toán có dạng :

Log2n	n	nlog2n	n2	n3	2n
0	1	0	1	1	2
1	2	2	4	8	4
2	4	8	16	64	16
3	8	24	64	512	256
4	16	64	256	40963	65536
5	32	160	1024	32768	2.147.483.648

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

log2n, n, nlog2, n2, n3, 2n, n!, nn Sau đây là bảng giá trị của một số hàm đó

Hình 1.1. Bảng giá trị của một số hàm số

Các hàm như 2n , n!, nn được gọi là hàm loại mũ. Một thuật toán mà thời gian

thực hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các hàm như n3 , n2, nlog2n, n, log2n được gọi là các hàm loại đa thức. Một thuật toán mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện, còn các thuật toán có độ phức tạp hàm mũ thì phải tìm cách cải tiến thuật toán.

Các quy tắc xác định độ phức tạp của thuật toán:

Xác định độ phức tạp tính toán của một thuật toán bất kỳ có thể dẫn tới những bài toán phức tạp. Tuy nhiên, trong thực tế, đối với một số thuật toán ta cũng có thể phân tích được bằng một số quy tắc đơn giản.

* Quy tắc tổng:

Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi thực hiện P1 và tiếp theo là P2 sẽ là: T1(n) + T2(n) = O(max (f(n),g(n))

Chứng minh:

Vì T1(n) = O(f(n)); T2(n) = O(g(n)) nên theo định nghĩa tồn tại các hằng số dương c1 , n1 và c2 , n2 sao cho:

T1(n) ≤ c1  f(n), với mọi n > n1 T2(n) ≤ c2  g(n) với mọi n > n2.

Chọn c = c1 + c2; n0 = max {n1, n2}.

Khi đó: T1(n) + T2(n)  c1  f(n) + c2  g(n)  c  max(f(n), g(n)) , với mọi n

> n0.

Do vậy: O(f(n)) + O(g(n)) = O(max(f(n), g(n))).

Ví dụ 1.1.

Trong một chương trình có 3 bước thực hiện mà độ phức tạp tính toán từng bước lần lượt là O(n2), O(n3) và O(nlog2n) thì độ phức tạp tính toán hai bước đầu là O(max (n2, n3) = O(n3). Độ phức tạp tính toán của chương trình sẽ là: O(max(n3, nlog2n)) = O(n3).

Nhận xét:

Từ quy tắc này có thể nhận thấy rằng: nếu g(n) ≤ f(n) với mọi n ≥ n0 thì: O(f(n)+g(n)) = O(f(n)).

Chẳng hạn: O(n4+n2) = O(n4)

O(n + log2n) = O(n).

* Quy tắc nhân:

Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi P1 và P2 lồng nhau sẽ là: T1(n).T2(n) = O(f(n).g(n))

Chứng minh:

Ta có: T1(n) = O(f(n)), T2(n) = O(g(n) theo định nghĩa tồn tại các hằng số dương c1 , n1và c2 , n2 sao cho:

T1(n) ≤ c1  f(n), với mọi n > n1 T2(n) ≤ c2  g(n) với mọi n > n2.

Chọn c = c1 * c2; n0 = max {n1, n2}.

Khi đó: T1(n).T2(n)  c1  f(n)  c2  g(n) = c  (f(n) g(n)).

Do vậy: T1(n).T2(n) = O(f(n).g(n)).

Ví dụ 1.2.

Câu lệnh gán : x = x+1 có thời gian thực hiện bằng c (hằng số) nên được đánh giá là O(1).

Câu lệnh: for ( i=1; i<=n; i++) x =x+1; Có độ phức tạp tính toán O(n.1) = O(n) Câu lệnh : for ( i= 1; i<=n; i++)

for ( j= 1; j<=n; j++) x =x+1;

có độ phức tạp tính toán được đánh giá là: O(n.n)=O(n2)

Nhận xét:

Từ quy tắc nhân ta sẽ có:

O(cf(n)) = O(f(n)) Chẳng hạn O(n2/2) = O(n2)

Chú ý :

Dựa vào những nhận xét đã nêu ở trên về quy tắc khi đánh giá độ phức tạp tính toán của thuật toán ta chỉ cần chú ý tới các bước tương tự với một phép toán mà ta gọi là phép toán tích cực. Đó là một phép toán thuộc thuật toán mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép toán khác (tất nhiên phép toán tích cực không phải là duy nhất) hay nói một cách khác: số lần thực hiện nó không kém gì các phép toán khác.