Các khái niệm cơ BẢN



tải về 0.5 Mb.
trang1/6
Chuyển đổi dữ liệu15.04.2018
Kích0.5 Mb.
  1   2   3   4   5   6

Phân tích và đánh giá độ phúc tạp thuật toán Nguyễn Thế Vinh - ĐHKH


CHƯƠNG 1

CÁC KHÁI NIỆM CƠ BẢN



1.1. KHÁI NIỆM BÀI TOÁN

1.1.1. Bài toán

Trong phạm vi Tin học, ta có thể quan niệm bài toán là việc nào đó mà ta muốn máy tính thực hiện.

Chẳng hạn như viết một dòng chữ ra màn hình, giải phương trình bậc hai, quản lí điểm trong trường học v.v… là những ví dụ về bài toán trong tin học.

Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: đưa vào máy thông tin gì (Input) và cần lấy ra thông tin gì (Output). Do đó để phát biểu một bài toán ta cần phải chỉ rõ Input và Output của bài toán đó.



Ví dụ 1: Giải phương trình bậc nhất ax+b=0

Input: Các giá trị thực a,b

Output: Nghiệm là giá trị x hoặc thông báo không có nghiệm

Ví dụ 2: Quản lý điểm trong trường học

Input: Thông tin cá nhân của từng học sinh

Output: Thông tin cần khai thác về điểm một học sinh, một lớp học sinh, một khối hay toàn trường.

1.1.2. Các bước giải bài toán bằng máy tính điện tử

Học sử dụng máy tính thực chất là học cách giao cho máy tính việc mà ta muốn nó làm. Khả năng khai thác máy tính phụ thuộc rất nhiều vào sự hiểu biết của người sử dụng. Giải bài toán trên máy tính được tiến hành qua các bước sau:


Bước 1: Xác định bài toán


Như đã trình bày ở trên, mỗi bài toán được đặc tả bởi hai thành phần: Input và Output. Việc xác định bài toán chính là xác định rõ hai thành phần này. Các thông tin đó cần được nghiên cứu cẩn thận để có thể lựa chọn thuật toán, cách thể hiện các đại lượng đã cho và các đại lượng phát sinh trong quá trình giải bài toán và ngôn ngữ lập trình thích hợp.

Ví dụ, trong một bài toán Tin học khi đề cập đến một số nguyên dương N ta phải biết rõ phạm vi giá trị của nó, để lựa chọn cách thể hiện N bằng kiểu dữ liệu thích hợp.


Bước 2: Lựa chọn hoặc thiết kế thuật toán


Bước lựa chọn và thiết kế thuật toán là bước quan trọng nhất để giải một bài toán.

Mỗi thuật toán chỉ giải một bài toán hoặc một lớp bài toán nào đó, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán. Cần chọn một thuật toán phù hợp để giải bài toán đã cho.

Khi lựa chọn thuật toán người ta thường quan tâm đến các tài nguyên như giờ CPU, số lượng ô nhớ,... Trong các loại tài nguyên, người ta quan tâm nhiều nhất đến thời gian vì đó là dạng tài nguyên không tái tạo được.

Trong thực tế, khi lựa chọn thuật toán người ta còn quan tâm tới việc viết chương trình cho thuật toán đó được dễ dàng.

Việc thiết kế và lựa chọn thuật toán để giải một bài toán cụ thể cần căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép.

Bước 3: Viết chương trình

Viết chương trình là việc tổng hợp hữu cơ giữa việc lựa chọn cấu trúc dữ liệu và ngôn ngữ lập trình để diễn đạt đúng thuật toán.

Khi viết chương trình ta cần lựa chọn một ngôn ngữ bậc cao, hoặc hợp ngữ, hoặc ngôn ngữ máy, hoặc một phần mềm chuyên dụng thích hợp cho thuật toán đã lựa chọn. Viết chương trình trong ngôn ngữ nào ta cần phải tuân theo đúng quy định ngữ pháp của ngôn ngữ đó. Chương trình dịch có thể giúp ta phát hiện và thông báo đầy đủ các sai sót về mặt ngữ pháp.

Bước 4: Hiệu chỉnh

Sau khi được viết xong, chương trình vẫn còn có thể có nhiều lỗi khác chưa phát hiện được nên chương trình có thể không cho kết quả đúng. Vì vậy, cần phải thử chương trình bằng cách thực hiện nó với một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bài toán. Các bộ Input này gọi là các Test. Nếu có sai sót, ta phải sửa chương trình rồi thử lại. Quá trình này được gọi là hiệu chỉnh.



Bước 5: Viết tài liệu

Tài liệu phải mô tả chi tiết bài toán, thuật toán, chương trình, kết quả thử nghiệm và hướng dẫn sử dụng. Tài liệu này rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm.

Các bước trên có thể lặp đi lặp lại nhiều lần cho đến khi mà ta cho là chương trình đã làm việc đúng đắn.

1.2. KHÁI NIỆM THUẬT TOÁN

1.2.1. Định nghĩa

Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán, ta nhận được Output cần tìm.

Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên; sơ đồ khối; ngôn ngữ lập trình(tựa Pascal).

1.2.2. Một số ví dụ

Ví dụ 1: Mô tả thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số bất kì (nguyên hoặc thực).

a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện:

1. Đặt giá trị cực đại tạm thời bằng số đầu tiên trong dãy.

2. So sánh số tiếp sau với giá trị cực đại tạm thời, nếu nó lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số đó.

3. Lặp lại bước 2 nếu còn các số trong dãy.

4. Dừng khi không còn số nào nữa trong dãy. Cực đại tạm thời ở điểm này chính là số lớn nhất của dãy.

b) Dùng ngôn ngữ tựa Pascal:

procedure max (a­1, a2, ..., an: Item);

begin

max:= a1;



for i:= 2 to n

if max i then max:= ai;

{max là phần tử lớn nhất}



end;

{Item quy ước là một kiểu dữ liệu bất kì nào đó}



Ví dụ 2: Mô tả thuật toán tìm tổng các phần tử dương trong một dãy hữu hạn các số bất kì.

a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện:

1. Đặt giá trị tổng ban đầu bằng 0.

2. Đi từ đầu dãy tới cuối dãy, kiểm tra số hiện thời nếu dương thì cộng giá trị đó vào tổng S.

3. Dừng khi không còn số nào nữa trong dãy. Giá trị S chính là tổng cần tìm.



b) Dùng ngôn ngữ tựa Pascal:

procedure Sum(a­1, a2, ..., an: Item);

begin

S:= 0;


for i:= 1 to n

if ai >0 then S:= S+ ai;

{S là tổng các phần tử dương}



end;

1.2.3. Các đặc trưng của thuật toán

Tính hữu hạn: Sau một số hữu hạn lần thực hiện các thao tác thuật toán phải kết thúc;

Tính xác định: Sau khi thực hiện một thao tác, hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo;

Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm;

Tính chi tiết: Các thao tác trong thuật toán phải được xác định một cách chặt chẽ theo nghĩa đủ chi tiết để đối tượng thực hiện thuật toán có thể làm được;

Tính phổ dụng: Thuật toán không chỉ cho phép giải một bài toán đơn lẻ mà áp dụng cho cả một lớp bài toán có cùng cấu trúc.

1.3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

1.3.1 Khái niệm về độ phức tạp của một thuật toán

Thước đo hiệu quả của một thuật toán là thời gian mà máy tính sử dụng để giải bài toán theo thuật toán đang xét, khi các giá trị đầu vào có một kích thước xác định. Một thước đo thứ hai là dung lượng bộ nhớ đòi hỏi để thực hiện thuật toán khi các giá trị đầu vào có kích thước xác định. Các vấn đề như thế liên quan đến độ phức tạp tính toán của một thuật toán. Sự phân tích thời gian cần thiết để giải một bài toán có kích thước đặc biệt nào đó liên quan đến độ phức tạp thời gian của thuật toán. Sự phân tích bộ nhớ cần thiết của máy tính liên quan đến độ phức tạp không gian của thuật toán. Việc xem xét độ phức tạp thời gian và không gian của một thuật toán là một vấn đề rất thiết yếu khi các thuật toán được thực hiện. Biết một thuật toán sẽ đưa ra đáp số trong một micro giây, trong một phút hoặc trong một tỉ năm, hiển nhiên là hết sức quan trọng. Tương tự như vậy, dung lượng bộ nhớ đòi hỏi phải là khả dụng để giải một bài toán, vì vậy độ phức tạp không gian cũng cần phải tính đến, vì việc xem xét độ phức tạp không gian gắn liền với các cấu trúc dữ liệu đặc biệt được dùng để thực hiện thuật toán nên ở đây ta sẽ tập trung xem xét độ phức tạp thời gian.

Độ phức tạp thời gian của một thuật toán có thể được biểu diễn qua số các phép toán được dùng bởi thuật toán đó khi các giá trị đầu vào có một kích thước xác định. Sở dĩ độ phức tạp thời gian được mô tả thông qua số các phép toán đòi hỏi thay vì thời gian thực của máy tính là bởi vì các máy tính khác nhau thực hiện các phép tính sơ cấp trong những khoảng thời gian khác nhau. Hơn nữa, phân tích tất cả các phép toán thành các phép tính bit sơ cấp mà máy tính sử dụng là điều rất phức tạp.

Ví dụ: Xét thuật toán tìm số lớn nhất trong dãy n số a1, a2, ..., an. Có thể coi kích thước của dữ liệu nhập là số lượng phần tử của dãy số, tức là n. Nếu coi mỗi lần so sánh hai số của thuật toán đòi hỏi một đơn vị thời gian (giây chẳng hạn) thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là n-1 giây. Với dãy 64 số, thời gian thực hiện thuật toán nhiều lắm là 63 giây. Ta nói độ phức tạp là n-1.

Ví dụ: Thuật toán về bài toán “Tháp Hà Nội”

Bài toán trò chơi “Tháp Hà Nội” như sau: Có ba cọc A, B, C bằng kim cương và 64 cái đĩa bằng vàng các đĩa có đường kính đôi một khác nhau. Nguyên tắc chuyển đĩa là: mỗi lần chỉ chuyển một đĩa và không được chồng đĩa to lên trên đĩa nhỏ hơn nó. Ban đầu, cả 64 đĩa được đặt chồng lên nhau ở cột A; hai cột B, C trống. Vấn đề là phải chuyển cả 64 đĩa đó từ cột A sang cột B lấy cột C làm trung gian.

Xét trò chơi với n đĩa ban đầu ở cọc A (cọc B và C trống). Gọi Sn là số lần chuyển đĩa để chơi xong trò chơi với n đĩa.

Nếu n=1 thì rõ ràng là S1=1.

Nếu n>1 thì trước hết ta chuyển n-1 đĩa bên trên sang cọc B (giữ yên đĩa thứ n ở dưới cùng của cọc A). Số lần chuyển n-1 đĩa là Sn-1. Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, ta chuyển n-1 đĩa từ cọc B sang cọc C (số lần chuyển là Sn-1).

Như vậy, số lần chuyển n đĩa từ A sang C là:

Sn=Sn-1+1+Sn-1=2Sn-1+1=2(2Sn-2+1)+1

=22Sn-2­+2+1=.....=2n-1S1+2n-2+...+2+1=2n1.

Thuật toán về bài toán “Tháp Hà Nội” đòi hỏi 2641 lần chuyển đĩa (xấp xỉ 18,4 tỉ tỉ lần). Nếu mỗi lần chuyển đĩa mất 1 giây thì thời gian thực hiện thuật toán xấp xỉ 585 tỉ năm. Ta nói độ phức tạp là 2n1

Hai thí dụ trên cho thấy rằng: một thuật toán phải kết thúc sau một số hữu hạn bước, nhưng nếu số hữu hạn này quá lớn thì thuật toán không thể thực hiện được trong thực tế.



1.3.2 So sánh độ phức tạp của các thuật toán

Một bài toán thường có nhiều cách giải, có nhiều thuật toán để giải, các thuật toán đó có độ phức tạp khác nhau.

Xét bài toán: Tính giá trị của đa thức P(x)=anxn+an-1xn-1+ ... +a1x+a0 tại x0.

Thuật toán 1

Procedure tính giá trị của đa thức (a0, a1, ..., an, x0: real);

begin

S:=a0

for i:=1 to n do

S:=S+aix0i­­;



end;

{S là giá trị của đa thức P(x) tại x0}

Chú ý rằng đa thức P(x) có thể viết dưới dạng:

P(x)=(...((anx+an-1)x+an-2)x...)x+a0.

Ta có thể tính P(x) theo thuật toán sau:

Thuật toán 2

Procedure tính giá trị của đa thức (a0, a1, ..., an, x0: real);

begin

P:=an

for i:=1 to n do

P:=P.x0+an-i;



end;

{P là giá trị của đa thức P(x) tại x0}

Ta hãy xét độ phức tạp của hai thuật toán trên.

Đối với thuật toán 1: ở bước 2, phải thực hiện 1 phép nhân và 1 phép cộng với i=1; 2 phép nhân và 1 phép cộng với i=2, ..., n phép nhân và 1 phép cộng với i=n. Vậy số phép tính (nhân và cộng) mà thuật toán 1 đòi hỏi là:

(1+1)+(2+1)+ ... +(n+1)=+n=.

Đối với thuật toán 2, bước 2 phải thực hiện n lần, mỗi lần đòi hỏi 2 phép tính (nhân rồi cộng), do đó số phép tính (nhân và cộng) mà thuật toán 2 đòi hỏi là 2n.

Nếu coi thời gian thực hiện mỗi phép tính nhân và cộng là như nhau và là một đơn vị thời gian thì với mỗi n cho trước, thời gian thực hiện thuật toán 1 là n(n+3)/2, còn thời gian thực hiện thuật toán 2 là 2n.

Rõ ràng là 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 1. Hàm f1(n)=2n là hàm bậc nhất, tăng chậm hơn nhiều so với hàm bậc hai f2(n)=n(n+3)/2.

Ta nói rằng thuật toán 2 (có độ phức tạp là 2n) là thuật toán hữu hiệu hơn (hay nhanh hơn) so với thuật toán 1 (có độ phức tạp là n(n+3)/2).

Để so sánh độ phức tạp của các thuật toán, điều tiện lợi là coi độ phức tạp của mỗi thuật toán như là cấp của hàm biểu hiện thời gian thực hiện thuật toán ấy.

Các hàm xét sau đây đều là hàm của biến số tự nhiên n>0.

Định nghĩa 1

Ta nói hàm f(n) có bậc thấp hơn hay bằng g(n) nếu tồn tại hằng số c>0 và một số tự nhiên n0 sao cho:

0 ≤ f(n)  c.g(n) với  n n0.

Ta viết f(n)=O(g(n)) và nói f(n) thoả mãn quan hệ big-O (O lớn) đối với g(n).

Kí hiệu O là giới hạn tiệm cận trên

Ví dụ hàm f(n)=a.n2+b.n+c =O(n2). Thật vậy với a>0 mọi hàm tuyến tính a.n+b đều thuộc vào O(n2).

Do vậy chỉ cần chọn hằng số c=a +|b| và n0= max(1,-b/a)

Định nghĩa 2

Ta nói hàm f(n) có bậc ít nhất là g(n) nếu tồn tại hằng số c>0 và số tự nhiên n0 sao cho:

f(n) ≥ c.g(n) ≥ 0 với  n n0.

Ta viết f(n)=Ω(g(n)) và nói f(n) thỏa mãn quan hệ Omega (Ω lớn) đối với g(n).

Kí hiệu Ω là giới hạn tiệm cận dưới

Ví dụ f(n)=2n2+ 3n+1 = Ω(n2). Thật vậy ta luôn có f(n) ≥ 2n2 = 2.g(n) với mọi số tự nhiên n và g(n)=n2. ta chọn hằng số c=2



Định nghĩa 3

Ta nói hàm f(n) có bậc là g(n) nếu tồn tại hằng số c1,c2 và một số tự nhiên n0 sao cho:

0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n) với  n  n0.

Ta viết f(n)=(g(n)) và nói f(n) thỏa mãn quan hệ Theta () đối với g(n).

Ta gọi g(n) là một tiệm cận ràng buộc chặt chẽ cho f(n).

Yêu cầu mỗi phần tử f(n)  (g(n)) phải tiệm cận không âm

Kí hiệu là tiệm cận ràng buộc chặt chẽ

Ví dụ f(n)=(1/2).n2 – 3.n= (n2). Thật vậy ta chỉ ra được các hằng số c1, c2 và n0 sao cho

c1.n2 ≤ (1/2)n2- 3.n ≤ c2.n2, với mọi n>n0.

Chia cho n2 ta được c1 ≤ (1/2)- 3/n ≤ c2. Như vậy với mỗi số tự nhiên n ta luôn tìm được các giá trị c1, c2 và n0 thỏa mãn.



Định lí 1: Với bất kì hàm f(n) và g(n), ta có f(n)= (g(n)) khi và chỉ khi f(n)=O(g(n)) và f(n)= Ω(g(n))

Chứng minh: Hiển nhiên theo định nghĩa ta có được điều kiện cần và đủ.

Ta lấy một ví dụ thực tiễn áp dụng cho định lí này đó là nghiệm của phương trình a.n2+b.n+c=0. Nghiệm của phương trình a.n2+b.n+c= (n2), với các hằng số a, b, c và a>0 ta có a.n2+b.n+c= O(n2) và a.n2+b.n+c= Ω(n2). Trong thực tế để đạt được tiệm cận trên và dưới từ tiệm cận ràng buộc chặt chẽ ta thường sử dụng nó để cải tiến tiệm cận ràng buộc chặt chẽ từ tiệm cận trên và dưới.

Dưới đây là đồ thị minh họa cho , OΩ (n0 là giá trị nhỏ nhất có thể)


c2g(n)

f(n)


c1g(n)

n0

f(n)= (g(n))


c.g(n)

f(n)


n0

f(n)=O(n)



f(n)


c.g(n)

n0

F(n)= Ω(g(n))



Ví dụ 1

Đánh giá tốc độ tăng của hàm .

Ta có

Ta đặt g(n)= n2

Ta có với n ≥ n0 =1

suy ra f(n) ≤c1.g(n) với c1=1; vậy f(n)=O(n2)

Mặt khác với n ≥ n0 =1

suy ra f(n) ≥c2.g(n) với c2=1/2 vậy f(n)=(n2). Do vậy f(n)= (g(n)) =(n2)

Theo định nghĩa này, hàm g(n) là một hàm đơn giản nhất có thể được, đại diện cho “sự biến thiên” của f(n).

Khái niệm big-O đã được dùng trong toán học đã gần một thế kỷ nay. Trong tin học, nó được sử dụng rộng rãi để phân tích các thuật toán. Nhà toán học người Đức Paul Bachman là người đầu tiên đưa ra khái niệm big-O vào năm 1892.



Ví dụ 2

Chứng tỏ rằng hàm f(n)= là hàm bậc hai và hàm bậc hai đơn giản nhất là n2.

Ta có:

f(n)==O(n2) vì  n2 với mọi n3 (c=1, n0=3).



Một cách tổng quát, nếu f(n)=aknk+ak-1nk-1+ ... +a1n+a0 thì f(n)=O(nk). Thật vậy, với n>1,

|f(n)||  |ak|nk+|ak-1|nk-1+ ... +|a1|n+|a0| = nk(|ak|+|ak-1|/n+ ... +|a1|/nk-1+a0/nk)

 nk(|ak|+|ak-1|+ ... +|a1|+a0).

Điều này chứng tỏ |f(n)|  Cnk với mọi n>1.



Ví dụ 3

Cho g(n)=3n+5nlog2n chứng minh rằng g(n)=O(nlog2n).

Thật vậy: 3n+5nlog2n = n(3+5log2n)  n(log2n+5log2n) = 6nlog2n với  n8 (c=6, n0=8).

Định lí 2: Cho f1(n)=O(g1(n)) và f2(n)=O(g2(n)). Khi đó

(f1 + f2)(n) = O(max(|g1(n)|,|g2(n)|), (f1.f2)(n) = O(g1(n)g2(n)).



Chứng minh. Theo giả thiết, tồn tại C1, C2, n1, n2 sao cho

|f1(n)|  C1|g1(n)| và |f2(n)|  C2|g2(n)| với  n > n1 và n > n­2.

Do đó |(f1 + f2)(n)| = |f1(n) + f2(n)|  |f1(n)| + |f2(n)|  C1|g1(n)| + C2|g2(n)|  (C1+C2)g(n)

với  n > n0=max(n1,n2), ở đâyC=C1+C2 và g(n)=max(|g1(n)| , |g2(n)|).

|(f1.f2)(n)| = |f1(n)||f2(n)|  C1|g1(n)|C2|g2(n)|  C1C2|(g1g2)(n)| với n > n0=max(n1,n2).

Định nghĩa 4

Ta viết f(n)=o(g(n)) và nói f(n) thoả mãn quan hệ (o nhỏ) đối với g(n), nếu với bất kì hằng số c>0 tồn tại một số tự nhiên n0>0 sao cho:

0 ≤ f(n) < c.g(n) với  n n0.

Kí hiệu o là giới hạn trên mà không tiệm cận chặt chẽ.

Ví dụ 2n2=O(n2) là tiệm cận chặt chẽ nhưng 2n=O(n2) thì không

Định nghĩa 5

Ta viết f(n)=(g(n)) và nói f(n) thoả mãn quan hệ ( nhỏ) đối với g(n), nếu với bất kì hằng số c>0 tồn tại một số tự nhiên n0>0 sao cho:

0  c.g(n) < f(n) với  n n0.

Kí hiệu là giới hạn dưới mà không tiệm cận chặt chẽ.

Ví dụ n2/2=(n) nhưng n2/2  (n2)

Định nghĩa 6

Nếu một thuật toán có độ phức tạp là f(n) với f(n)=O(g(n)) thì ta cũng nói thuật toán có độ phức tạp O(g(n)).

Nếu có hai thuật toán giải cùng một bài toán, thuật toán 1 có độ phức tạp O(g1(n)), thuật toán 2 có độ phức tạp O(g2(n)), mà g1(n) có cấp thấp hơn g2(n), thì ta nói rằng thuật toán 1 hữu hiệu hơn (hay nhanh hơn) thuật toán 2.

1.3.3 Đánh giá độ phức tạp của một thuật toán

1.3.3.1 Thuật toán tìm kiếm tuyến tính

Số các phép so sánh được dùng trong thuật toán này cũng sẽ được xem như thước đo độ phức tạp thời gian của nó. Ở mỗi một bước của vòng lặp trong thuật toán, có hai phép so sánh được thực hiện: một để xem đã tới cuối bảng chưa và một để so sánh phần tử x với một số hạng của bảng. Cuối cùng còn một phép so sánh nữa làm ở ngoài vòng lặp. Do đó, nếu x=ai, thì đã có 2i+1 phép so sánh được sử dụng. Số phép so sánh nhiều nhất, 2n+2, đòi hỏi phải được sử dụng khi phần tử x không có mặt trong bảng. Từ đó, thuật toán tìm kiếm tuyến tính có độ phức tạp là O(n).



Procedure search;

begin

i:=1;


found:=flase;

While (i<=n) and (not found) do

if (x=a[i]) then

found:=true

else i:=i+1;

if (found) then

write(‘Yes’)

else write(‘No’);



end;

1.3.3.2 Thuật toán tìm kiếm nhị phân

Để đơn giản, ta giả sử rằng có n=2k phần tử trong bảng liệt kê a1,a2,...,an, với k là số nguyên không âm (nếu n không phải là lũy thừa của 2, ta có thể xem bảng là một phần của bảng gồm 2k+1 phần tử, trong đó k là số nguyên nhỏ nhất sao cho n < 2k+1).

Ở mỗi giai đoạn của thuật toán vị trí của số hạng đầu tiên d và số hạng cuối cùng c của bảng con hạn chế tìm kiếm ở giai đoạn đó được so sánh để xem bảng con này còn nhiều hơn một phần tử hay không. Nếu d < c, một phép so sánh sẽ được làm để xác định x có lớn hơn số hạng ở giữa của bảng con hạn chế hay không. Như vậy ở mỗi giai đoạn, có sử dụng hai phép so sánh. Khi trong bảng chỉ còn một phần tử, một phép so sánh sẽ cho chúng ta biết rằng không còn một phần tử nào thêm nữa và một phép so sánh nữa cho biết số hạng đó có phải là x hay không. Tóm lại cần phải có nhiều nhất 2k+2=2log2n+2 phép so sánh để thực hiện phép tìm kiếm nhị phân (nếu n không phải là lũy thừa của 2, bảng gốc sẽ được mở rộng tới bảng có 2k+1 phần tử, với k=[log2n] và sự tìm kiếm đòi hỏi phải thực hiện nhiều nhất 2[log2n]+2 phép so sánh).

Do đó thuật toán tìm kiếm nhị phân có độ phức tạp là O(log2n). Từ sự phân tích ở trên suy ra rằng thuật toán tìm kiếm nhị phân, ngay cả trong trường hợp xấu nhất, cũng hiệu quả hơn thuật toán tìm kiếm tuyến tính.



Procedure binary search;

begin

d:=1;


c:=n;

found:=false;

while (d<=c) and (not found) do

begin


i:=(d+c) div 2;

if (x=ai) then

found:=true

else


if (x> ai ) then

d:=i+1


else c:=i-1;

end;


if found then

write(‘Yes’)

else write(‘No’);

end;

1.3.4 Các thuật ngữ thường dùng


Độ phức tạp

Thuật ngữ

O(1)

Độ phức tạp hằng số

O(logn)

Độ phức tạp lôgarit

O(n)

Độ phức tạp tuyến tính

O(nlogn)

Độ phức tạp nlogn

O(nb)

Độ phức tạp đa thức

O(bn) (b>1)

Độ phức tạp hàm mũ

O(n!)

Độ phức tạp giai thừa

1.4 Đánh giá thời gian thực hiện thuật toán

1.4.1 Tính độc lập

Tốc độ thực hiện một chương trình là khoảng thời gian từ INPUT có được OUTPUT của bài toán. Tuy nhiên tốc độ thực hiện một chương trình phụ thuộc vào ngôn ngữ lập trình, chương trình dịch, hệ điều hành, phần cứng của máy… Mặt khác, phải lập trình mới đo được thời gian thực hiện của thuật toán.

Cần đánh giá thời thực hiện sao cho:

- Không phụ thuộc máy, ngôn ngữ lập trình, chương trình biên dịch;

- Không cần phải triển khai chương trình thực hiện thuật toán;

- Chỉ dựa vào bản thân thuật toán.

Trong 2 thuật toán, ta đã tính thời gian thực hiện thuật toán bằng số phép tính cần tiến hành. Đây chính là cách làm đáp ứng nhu cầu trên.

1.4.2 Các phép toán sơ cấp

Các phép toán sơ cấp là những phép toán mà thời gian thực hiện nó đủ ngắn, hay nói đúng hơn là không vượt quá một hằng số nào đó. Các phép toán sau đây có thể coi là sơ cấp:

- Các phép tính số học;

- Các phép tính logic;

- Các phép chuyển chỗ, phép gán;

- Lời gọi các thủ tục.


1.4.3 Kích thước dữ liệu đầu vào

Cho một thuật toán ta hoàn toàn ước lượng được tổng số các phép toán sơ cấp cần thiết để thực hiện thuật toán đó. Một điều hiển nhiên là tổng số phép toán sơ cấp để giải một bài toán phụ thuộc vào kích thước của bài toán. Dùng cùng một thuật toán, tính một định thức cấp 5 rõ ràng cần ít phép tính hơn định thức cấp 10. Tổng số mục dữ liệu đầu vào là đặc trưng cho kích thước của bài toán. Người ta thường dùng một số nguyên dương n để thể hiện kích thước này.

Như vậy, một thuật toán T áp dụng để giải bài toán có kích thước n sẽ cần một tổng số T(n) các phép toán sơ cấp. T(n) là một hàm của tham số n. Hàm số T(n) là đặc trưng cho hiệu quả của thuật toán T.

1.4.4 Tình trạng dữ liệu đầu vào

Không chỉ có số lượng dữ liệu đầu vào quyết định thời gian thực hiện giải thuật mà tình trạng dữ liệu cũng ảnh hưởng đến việc thuật toán thực hiện nhanh hay chậm.

Xét bài toán sắp xếp đơn điệu một dãy số. Rõ ràng là nếu dãy đã có sẵn thứ tự mong muốn hoặc gần thư thế thì công việc phải làm ít hơn trường hợp một dãy bất kỳ.

Hoặc bài toán tìm kiếm tuần tự trong một dãy số cho sẵn như tìm vị trí của phần tử k trong mảng a[1.. n] (nếu k ở vị trí đầu tiên hoặc k không tồn tại trong mảng a)

- Trường hợp mới bắt đầu tìm kiếm gặp ngay phần từ k thì đây là trường hợp tốt nhất (best case) T(n) = 1.

- Trường hợp tìm kiếm mà không có k trong mảng hay k nằm ở cuối mảng thì đây là trường hợp xấu nhất, phải duyệt qua tất cả các phần tử của mảng a[1..n] (worst case). T(n) = n.

- Trường hợp trung bình T(n) = 0, 5. p(n + 1) + n(1 – p).

Tùy theo tình trạng dữ liệu đầu vào mà ta có các trường hợp:

- Thời gian tốt nhất T(n) là thời gian thực hiện nhanh nhất của thuật toán với một bộ dữ liệu nào đó, ta ký hiệu là Tmin (best case).

- Thời gian tồi nhất T(n) là thời gian thực hiện chậm nhất của thuật toán với một bộ dữ liệu nào đó, ta ký hiệu là Tmax (worst case).

- Thời gian tính trung bình T(n) là trung bình cộng của các thời gian thực hiện thuật toán với các bộ dữ liệu khác nhau nào đó, ta ký hiệu là Taver (average case).

Trong thực tế ta thường dùng thời gian thực hiện trung bình Taver để so sánh đánh giá thuật toán. Nếu việc tính thời gian thực hiện trung bình quá khó khăn, có thể đánh giá căn cứ vào trường hợp xấu nhất, tức là dùng Tmax. Đôi khi, nhiều bài toán thời gian thực đòi hỏi thời gian trả lời phải không vượt quá một giới hạn cho phép nào đó (ví dụ như bài toán dự báo thời tiết). Trong trường hợp này, chỉ có thể dùng ước lượng trong trường hợp xấu nhất, nghĩa là Tmax mà thôi.



1.4.5 Các xác định thời gian thực hiện một thuật toán

1.4.5.1 Thời gian thực hiện các câu lệnh trong lập trình

Gọi fi(n) là thời gian thực hiện câu lệnh Si. Khi đó thời gian thực hiện các câu lệnh trong lập trình được quy ước như sau:

- Câu lệnh đơn: các câu lệnh đơn như gán, đọc, viết, so sánh,… có thời gian thực hiện là O(1);

- Câu lệnh ghép: S = S1 + S2 + …+ Sp; tính thời gian thực hiện theo quy tắc tổng;

- Câu lệnh rẽ nhánh: if <điều kiện> f1 else f2; tính thời gian thực hiện là O(max { f1(n), f2(n) });

Ví dụ trong đoạn chương trình sau:



if n>1 then

for i:=1 to n do write(i)

else

write(n);

T(n)=O(max(1, n))=O(n)

- Câu lệnh lựa chọn: case tính thời gian tương tự như if;

- Vòng lặp: While< điều kiện> do{ f } ;

tính thời gian thực hiện là f(n)= (số lần lặp) *{f}

Ví dụ trong đoạn chương trình sau



for i:=1 to n do

begin

tg:=a;

a:=b;

b:=tg;

end;

T(n)=O(n.3)=O(n)

- Vòng lặp: For tương tự như While.
Ví dụ 1 Tính T(n) đối với thuật toán tính tổng sau


Thủ tục

Số phép tính

Procedure summarize;

begin

write(‘Vào n:’);

readln(n);

S:=0;


for i:=1 to n do

begin


write(‘Vào giá trị:’);

readln(x);

s:=s+x;

end;


writeln(‘Tong la:’,S)

end;

1

1

1



n

n

2n



1


Tổng số phép tính T(n)

4n+4


Ví dụ 2 Tính T(n) đối với thuật toán tìm kiếm sau

Thủ tục

Số phép tính

Procedure search;

begin

i:=1;


found:=flase;

While (i<=n) and (not found) do

if (x=a[i]) then found:=true

else i:=i+1;

if (found) then write(‘Yes’)

else write(‘No’);



end;

1

1

k



1


Tổng số phép tính: T(n)

k+3

Đối với đoạn chương trình trên ta thấy thời gian thực hiện thuật toán là T(n)=k+3 trong đó (1 ≤ k ≤ n)

Thời gian tốt nhất khi phần tử cần tìm là a[1]; Tmin (best case)=1+3=4;

Thời gian tồi nhất T(n) là khi không tìm được x; Tmax (worst case)=n+3.

Vậy để tính thời gian trung bình ta dựa vào nhận xét sau

Nếu x=a[1] thì T(n)=3+1;

Nếu x=a[2] thì T(n)=3+2;

Nếu x=a[n] thì T(n)=3+n;



Cuối cùng nếu không tìm thấy x thì T(n)=3+n; do vậy thời gian trung bình

Taver (average case) = [(3+1) + (3+2) + . . . +(3+n)+ (3+n)]/(n+1)

= (n2+9n+6)/[2(n+1)]

Ta sẽ đánh giá chi tiết hàm này ở phần sau.



Ví dụ 3 Tính T(n) đối với thuật toán sử dụng các vòng lặp lồng nhau

Cho ma trận A[n.m] xây dựng mảng B[n] trong đó B[i] là phần tử lớn nhất của hàng thứ i đối với ma trận A[n.m].

Giả sử phần tử max là phần tử cột đầu tiên của hàng i, lần lượt xét các cột tiếp theo nếu lớn hơn phần tử max thì ghi nhận trái lại chuyển sang cột tiếp theo và sử dụng chính b[i] là phần tử max


Thủ tục

Số phép tính

Procedure findmax;

begin

for i:=1 to n do

begin

b[i]:= a[i,1];



for j:=2 to m do

if (b[i]

end;

end;


n

2(m-1)n



Tổng số phép tính: T(n)

n+2n(m-1)

vậy T(n)=O(n2)



Ví dụ 4 Tính T(n) đối với thuật toán sử dụng các vòng lặp lồng nhau trong đoạn chương trình sau

Thủ tục

Số phép tính

Procedure sum;;

begin

for i:=1 to n do

begin

b[i]:=i;


for j:=1 to i do

S:=S+ b[i] *c[j];

end;

end;


n

[n(n+1)]3/2




Tổng số phép tính: T(n)

n+[n(n+1)]3/2

vậy T(n)=O(n2)


Ví dụ 5 Tính T(n) đối với thuật toán sử dụng các vòng lặp lồng nhau sau đây

Thủ tục

Số phép tính

Procedure findmax;

begin

for i:=1 to n do

begin

b[i]:=max(a[i,1]);



for j:=1 to m do

if (b[i]=c[j]) then

for k:=1 to n do S:=S+b[k]

else S:= S+c[j];

end;

end;


(n).n

m

2[(m).n]n



2(m).n


Tổng số phép tính: T(n)

n2+m+2m.n2

Điều kiện rẽ nhánh kết quả là Max(2m.n2,2m.n)

vậy T(n)=O(2m.n2)=O(n3)

1.4.5.2 Thời gian thực hiện khi dữ liệu đầu vào giảm

Trường hợp T(n)=T(n-1)+c

Ta có T(n)=T(n-1)+c=T(n-2)+2.c =… = T(1) + (n-1).c

Vậy T(n)=O(n)

Trường hợp T(n)=T(n/2)+c

Ta có T(n)=T(n/2)+c=T(n/22)+2.c =… = T(n/2k) + k.c

Mặt khác n/2k=1  k= log2n

Vậy T(n)=O(log2n)



Trường hợp T(n)=a.T(n/a)+c.n với (a>1)

Ta có T(n)=a.T(n/a)+c=a2.T(n/a2)+2.c =… =ak. T(n/ak) + k.c.n

Mặt khác n/ak=1  k= logan khi đó T(n)= n.T(1)+ n.logan.c

Vậy T(n)=O(n.logan)



Trường hợp T(n)=a.T(n/b)+c.nk với (a,b>1)

Ta có T(n)=O(nlogba) khi a>bk.

Ta có T(n)=O(nk.logan) khi a=bk.

Ta có T(n)=O(nk) khi ak.

Trong trường hợp ta chấp nhận kết quả để sử dụng cho việc đánh giá thuật toán ở các phần tiếp theo, bạn đọc có thể tự chứng minh.

1.4.5.2 Ví dụ minh họa

Vú dụ 1: Đánh giá tính tối ưu về thời gian các thuật toán

Tính ex = 1 + ( x/1!) + (x*x/2!) + (x*x*x/ 3!) + … + (xn /n!)



Thuật toán 1

procedure calculation1;

begin

S:=1;


for i:=1 to n do

begin


P:=1;

for j:=1 to i do P:=P*x/j;

S:=S+P;

end;


end;

Vòng for bên trong có số phép toán bằng i.


Tổng số phép toán T(n) =1+ n+ 3 (1 + 2+ … + n) + 2n

= 1+3n+ 3. [n( n +1 )]/ 2 = O(n2)



Thuật toán 2

Kế thừa, dùng kết quả của bước trước, tính số hạng sau qua số hạng trước.

x/n! = (x/n ) . (xn-1/(n-1)!)

procedure calculation2;

begin

S:=1; P:=1;

for i:=1 to n do

begin


P:=P*x/i; S:=S+P;

end;


end;

Tổng số phép toán T(n) = 2+ 5.n= O(n).

Như vậy thuật toán 2 tối ưu hơn thuật toán 1.

Ví dụ 2:

Đánh giá thời gian khi dữ liệu đầu vào tăng đủ lớn đối với các hàm sau

a. Hàm T(n)= n2+9n+6

Ta có T(n)= n2+9n+6 ≤ n2+9n2+n2= 11n2 với ( n ≥ 1);

Theo định nghĩa 1 nếu chọn c= 11 và g(n)=n2 ta được T(n)≤c.g(n)

Vậy T(n)=O(n2)

b. Hàm T(n)= n(n+1)/2

Ta có T(n)= n(n+1)/2= n2/2+n/2 ≤ n2/2 + n2/2= n2 với ( n ≥ 1);

Nếu chọn c=1; và g(n)=n2 thì T(n)=O(n2)

c. Hàm T(n)=(n2+1)/(n+1)

Ta có T(n)=(n2+1)/(n+1)=(n-1) + 2/(n+1) ≤ n với ( n ≥ 1)

Nếu chọn c=1 và g(n)=n thì T(n)=O(n)

d. Hàm T(n)=Taver (average case) = (n2+9n+6)/[2(n+1)]

Ta có T(n)= (n2+9n+6)/[2(n+1)] ≤ (n2+9n+6)/n = n+9+ 6/n với n đủ lớn thì 6/n dần tới 0 khi đó T(n)≤ (n+9) vậy T(n)=O(n)



1.4.6 Thời gian máy tính được dùng bởi một thuật toán

Kích thước

Các phép tính bit được sử dụng

n

logn

N

nlogn

n2

2n

n!

10

3.10-9 s

10-8 s

3.10-8 s

10-7 s

10-6 s

3.10-3 s

102

7.10-9 s

10-7 s

7.10-7 s

10-5 s

4.1013năm

*

103

1,0.10-8 s

10-6 s

1.10-5 s

10-3 s

*

*

104

1,3.10-8 s

10-5 s

1.10-4 s

10-1 s

*

*

105

1,7.10-8 s

10-4 s

2.10-3 s

10 s

*

*

106

2.10-8 s

10-3 s

2.10-2 s

17 phút

*

*

Nhìn vào bảng trên ta nhận thấy rằng thời gian máy tính thực hiện dùng bởi một thuật toán phụ thuộc rất lớn vào thuật toán và dữ liệu đầu vào áp dụng đối với thuật toán đó, điều này giúp chúng ta trong việc lựa chọn thuật toán phù hợp đáp ứng nhu cầu thực tiễn và tính khả thi của nó.



BÀI TẬP CHƯƠNG 1
Bài tập tính toán

1.1.1. Tìm một số nguyên n nhỏ nhất sao cho f(x) là O(xn) đối với các hàm f(x) tương ứng sau:

a) f(x) = 2x3 + x2log x.

b) f(x) = 2x3 + (log x)4.

c) f(x) =

d) f(x) = .

1.1.2. Cho một đánh giá big-O đối với các hàm cho dưới đây. Đối với hàm g(x) trong đánh giá f(x) là O(g(x)), hãy chọn hàm đơn giản có bậc thấp nhất.

a) nlog(n2 + 1) + n2logn.

b) (nlogn + 1)2 + (logn + 1)(n2 + 1).

1.1.3. Lập ít nhất 2 thuật toán tính xn với x là một số thực và n là một số nguyên. Đánh giá độ phức tạp của từng thuật toán.

1.1.4. Mô tả thuật toán chèn một số nguyên x vào vị trí thích hợp trong dãy các số nguyên a1, a2, ..., an xếp theo thứ tự tăng dần.

1.1.5. Tìm thuật toán xác định vị trí gặp đầu tiên của phần tử lớn nhất trong bảng liệt kê các số nguyên, trong đó các số này không nhất thiết phải khác nhau.

1.1.6. Tìm thuật toán đảo ngược một dãy số nguyên gồm n số. Đánh giá độ phức tạp của thuật toán đó.

1.1.7. Xác định xem (2p - 1) có là số nguyên tố không đối với mỗi số nguyên tố (2

1.1.8. Cho một số nguyên dương. Xây dựng thuật toán phân tích số đó ra thừa số nguyên tố

1.1.9. Cho một dãy n số nguyên phân biệt. Dùng thuật toán tìm kiếm nhị phân để xác định vị trí của một phần tử trong dãy đã cho.

1.1.10. Tìm một tập hợp gồm bốn số nguyên tố cùng nhau, sao cho không có hai số nào trong chúng là nguyên tố cùng nhau

Bài tập trên máy tính

1.2.1. Cho một dãy gồm n số nguyên a1, a2, ..., an . Tìm số nguyên lớn nhất, nhỏ nhất trong dãy đó

1.2.2. Cho một dãy gồm n số nguyên a1, a2, ..., an . Tìm số nguyên lớn thứ nhì trong dãy đó. Mở rộng bài toán cho trường hợp số lớn thứ K trong dãy.

1.2.3. Lập trình tính tổng hai số nguyên lớn có n chữ số (50
1.2.4. Chuyển đổi một số từ hệ đếm cơ số 10 sang hệ đếm cơ số 2; cơ số 8; cơ số 16 và ngược lại.

1.2.5. Cho một dãy gồm n số nguyên a1, a2, ..., an. Lập trình loại bỏ đi một số phần tử để dãy con còn lại là dãy tăng dài nhất

Viết tiểu luận

1.3.1. Hãy sưu tầm các thuật toán về số nguyên tố

1.3.2. Tìm hiểu những ứng dụng thực tiễn của số nguyên tố

1.3.3. Sưu tầm các phương pháp dùng để nén thông tin và giải nén lấy ví dụ minh họa cho mỗi phương pháp.

1.3.4. Mô tả thuật toán sắp xếp ngoài

1.3.5. Mô tả các thuật toán xử lí bít

CHƯƠNG 2



Поделитесь с Вашими друзьями:
  1   2   3   4   5   6


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©tieuluan.info 2019
được sử dụng cho việc quản lý

    Quê hương