SKKN Đánh giá độ phức tạp của thuật toán thông qua ví dụ

MỤC LỤC
A.	Phần mở đầu	1
I.	Lý do chọn đề tài	1
II.	Mục đích của đề tài	1
III.	Nhiệm vụ và phương pháp nghiên cứu	1
VI.	Điểm mới trong kết quả nghiên cứu	2
B. Nội dung..........................................................................................................3
I.	Khái niệm độ phức tạp của thuật toán............................................................3
II. 	Đánh giá độ phức tạp của thuật toán..............................................................3
2.1. Quy tắc đánh giá độ phức tạp thuật toán.......................................................3
2.2. Đánh giá độ phức tạp của thuật toán thông qua đề thi học sinh giỏi tỉnh Thanh hóa năm học 2016-2017............................................................................5
C. 	Phần kết luận.................................................................................................13A. PHẦN MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI
Trong quá trình tham gia giảng dạy và bồi dưỡng học sinh giỏi môn Tin học thì việc đánh giá độ phức tạp của thuật toán là một công việc hết sức quan trọng. Khi tiếp xúc trực tiếp với các giáo viên và học sinh phổ thông trong địa bàn tỉnh Thanh Hóa thì gần như có rất nhiều thầy cô và các em học sinh chưa hiểu rõ về cách đánh giá độ phức tạp của thuật toán. Trong các kỳ thi học sinh giỏi, nếu một thuật toán cho ra một kết quả đúng nhưng thời gian thực hiện thuật toán đó lớn hơn thời gian quy định thì bài làm đó sẽ không được điểm tối đa. Thông thường giới hạn thời gian của mỗi test trong kỳ thi chọn học sinh giỏi Tỉnh Thanh Hóa là 1giây (1s/1test). Với lại trên thực tế, tài liệu viết về cách đánh giá độ phức tạp của thuật toán còn hạn hẹp và việc tự đọc để hiểu tài liệu đó còn gặp nhiều khó khăn.
Từ các lí do trên, tôi xin trình bày sáng kiến kinh nghiệm “ ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN THÔNG QUA VÍ DỤ ”, để giúp giáo viên và học sinh có thể hiểu rõ hơn về cách đánh giá độ phức tạp của thuật toán.
II. MỤC ĐÍCH CỦA ĐỀ TÀI
Việc đánh giá độ phức tạp của thuật toán là hết sức quan trong trọng các kỳ thi học sinh giỏi và rất cần thiết. Đề tài này sẽ giúp giáo viên và học sinh có một tài liệu có thể tự đọc và hiểu được cách đánh giá độ phức tạp của thuật toán. Từ đó khi giải quyết một bài toán trong các kỳ thi học sinh giỏi: với cách làm của mình như thế thì tính được độ phức tạp là bao nhiêu? Khi biết đánh giá được độ phức tạp của bài toán thì sẽ biết bài đó mình được tầm bao nhiêu điểm?
III. NHIỆM VỤ VÀ PHƯƠNG PHÁP NGHIÊN CỨU
Viết sáng kiến kinh nghiệm thường xuyên liên tục cũng là nhiệm vụ chính trị của mỗi giáo viên, nhưng cần phải lựa chọn phương pháp nghiên cứu đúng đắn và phù hợp với nhà trường trung học phổ thông. Sáng kiến kinh nghiệm đang trình bày của tôi dựa theo các luận cứ khoa học hướng đối tượng, cụ thể: thuyết trình, quan sát, điều tra cơ bản, phân tích kết quả thực nghiệm sư phạm,v.v phù hợp với bài học và môn học thuộc lĩnh vực Tin học .
IV. ĐIỂM MỚI TRONG KẾT QUẢ NGHIÊN CỨU
Giúp cho hầu hết học sinh sau khi làm bài thì có thể biết mình được bao nhiêu điểm . Ngoài ra, tôi mạnh dạn trình bày sáng kiến kinh nghiệm này còn để phục vụ cho giáo viên trong quá trình dạy đội tuyển và rèn luyện cho học sinh cách đánh giá độ phức tạp của thuật toán.
B. PHẦN NỘI DUNG
I. KHÁI NIỆM ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
Nói về độ phức tạp của thuật toán thì độ phức tạp về thời gian là quan trọng nhất, bởi vì nếu một thuật toán cho ra một kết quả đúng nhưng thời gian thực hiện thuật toán cần một khoảng thời gian lớn đến nỗi không thể chấp nhận được (Ví dụ bài toán tháp Hà Nội nếu dùng đệ quy để tính toán thì với tốc độ máy tính hiện nay phải giải nó khoảng vài ngàn năm). Do đó yêu cầu thời gian được đưa ra đầu tiên. Thuật toán được gọi là hay thì phải có thời gian thực hiện ngắn và tiết kiệm tài nguyên máy tính. Sự hao phí tài nguyên máy tính liên quan đến phần cứng máy tính. Vì vậy mà những thuật toán đưa ra thường lấy thời gian để tính độ phức tạp hơn là tài nguyên (vì mỗi máy khác tài nguyên). Vì vậy, độ phức tạp của thuật toán là thời gian thực hiện của thuật toán. Ký hiệu độ phức tạp của thuật toán là O lớn. Ta có tính chất O(f(x)+g(x))=max (O(f(x)), O(g(x)))
II. ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
Quy tắc đánh giá độ phức tạp thuật toán
Ở đây chúng ta hiểu nôm na là đánh giá về mặt thời gian. Và cách hiểu thông thường nhất chính là số lần lặp tối đa của một đoạn chương trình.
Ví dụ 1:	Xét câu lệnh x:= x+1;
Độ phức tạp của câu lệnh trên là O(1). Vì đây là câu lệnh đơn nó được thực hiện 1 lần.
Ví dụ 2: Xét câu lệnh sau:
For i:= 1 to 10 do x:= x+ 1;
Câu lệnh trên được lặp 10 lần, mỗi lần lặp thì nó thực hiện một lệnh đơn x:= x+1 suy ra câu lệnh trên có độ phức tạp là O(10).
Ví dụ 3: Xét câu lệnh sau:
For i:= 1 to n do x:= x+ 1;
Câu lệnh trên được lặp n lần, nên độ phức tạp của thuật toán là O(n).
Ví dụ 4: Xét câu lệnh sau:
For i:= 1 to n do
For j:=1 to n do x:= x+ a;
	Đây là 2 câu lệnh For lồng nhau, nên nó lặp n2 lần, suy ra độ phức tạp của thuật toán là O(n2).
Ví dụ 5: Xét đoạn chương trình sau:
x:= 1;	//O(1)
for i:= 1 to n do x:= x+i;	//O(n)
for i:= 1 to n do
	for j:= 1 to n do x:= x+1;	//O(n2)
	Độ phức tạp của đoạn chương trình trên là max(O(1), O(n), O(n2)) = O(n2).
Ví dụ 6: Xét đoạn chương trình tìm kiếm nhị phân sau:
dau:=1; cuoi:= n;
 	while dau <= cuoi do
begin
 	giua:=(dau+cuoi) div 2;
 	if a[giua] = tim then
	begin
	writeln(’tim thay’);
	break;
	end
	else	
if a[giua] > tim then
 	cuoi:=giua -1;
 	 	else dau:= giua +1;
	end;
Câu lệnh dau:=1; cuoi:= n; là câu lệnh đơn có độ phức tạp là O(1). Còn cả khối lệnh phía sau là đoạn tìm kiếm nhị phân trên mảng có n phần tử a[1], a[2], a[3],... a[n]. Nó cứ chia đôi ra để tìm. Suy ra số lần tối đa của việc chia đôi ra chính là độ phức tạp của thuật toán. Giả sử số lần chia đôi là k, thì ta dễ dàng thấy 2k = n. Từ đây là suy ra k = log2n. Độ phức tạp của đoạn chương trình trên là O(log2 n) hay nói một cách ngắn gọn là O(log n).
Ví dụ 7: Xét đoạn chương trình sắp xếp sau:
For i:= 1 to n-1 do 
	For j:=i+1 to n do
	If a[i]>a[j] then
Begin
	Tg:= a[i];
	A[i]:= a[j];
	A[j]:= tg;
	End;
Ta thấy đoạn chương trình trên có cấu trúc for lồng nhau, còn sau lệnh for là các câu lệnh đơn
Khi i=1 thì nó lặp n-1 lần;
Khi i=2 thì nó lặp n-2 lần;
Khi i=3 thì nó lặp n-3 lần;
...........................
Khi i=n-1 thì nó lặp 1 lần;
Vậy số lần lặp tối đa của đoạn chương trình trên là: (n-1) + (n-2) + (n-3) + ... + 2 + 1. Đây là tổng các số tự nhiên từ 1 đến n-1. Áp dụng công thức cấp số cộng ta được kết quả là . Vậy độ phức tạp của thuật toán là O(). Khi n lớn thì ta có thể thấy độ phức tạp này sấp sĩ bằng O(n2).
Đánh giá độ phức tạp của thuật toán thông qua đề thi học sinh giỏi tỉnh Thanh hóa năm học 2016-2017
Như chúng ta đã biết trong các kỳ thi học sinh giỏi, thì 1 giây thì máy tính chạy được tầm 5.108 phép tính. Vì vậy nếu đề bài cho giới hạn của N ≤ 105 thuật toán của chúng ta làm phải bé hơn hoặc bằng O(nlog n) thì mới chạy được hết tất cả các test (có giới hạn 1s/1test). Còn nếu ta làm thuật toán có độ phức tạp là O(n2) thì không ăn hết được tất cả các test trong 1 giây. Ta chỉ cần tính đơn giản, khi n=105 thì n2=1010, mà theo trên thì 1010 phép tính thì nó không thể chạy trong 1 giây.
Bài 1: (5 điểm) Tổng nguyên tố
Cho số nguyên dương N (N ≤ 105).
Yêu cầu: Tìm số các cặp số nguyên dương x, y sao cho:
x, y là 2 số nguyên tố.
x + y = N
x ≤ y
Dữ liệu vào: Vào từ file văn bản BAI1.INP gồm một số duy nhất N.
Kết quả: Đưa ra file văn bản BAI1.OUT một số là số các cặp số tìm được.
Ví dụ:
BAI1.INP
BAI1.OUT
10
2
Code :
const fi='bai1.inp';
 fo='bai1.out';
var n,i,j: longint;
 res: longint;
function ngto(x: longint): boolean; //O(-1)
var i: longint;
begin
 ngto:= true;
 for i:= 2 to trunc(sqrt(x)) do
 if x mod i = 0 then
 begin
 ngto:= false;
 break;
 end;
end;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(n);
 res:=0;
 for i:=2 to n div 2 do
 if ngto(i) and ngto(n-i) then inc(res); 
 writeln(res);
 close(output);
END.
Rễ dàng nhận thấy độ phức tạp của thuật toán là O(()*)). Hay có thể hiểu ngắn gọn là O(n).
Bài 2: (5 điểm) Kí tự khác nhau
Cho xâu S chỉ gồm các kí tự là chữ cái tiếng anh và các chữ số (có phân biệt chữ in hoa, in thường). 
Yêu cầu: Hãy xác định số kí tự khác nhau trong xâu S và mỗi kí tự xuất hiện bao nhiêu lần.
Dữ liệu vào: Vào từ file văn bản BAI2.INP gồm 1 dòng duy nhất là xâu kí tự S (có độ dài không quá 255).
Kết quả: Kết quả ghi ra file văn bản BAI2.OUT gồm:
- Dòng đầu ghi số kí tự khác nhau.
- Các dòng tiếp theo, mỗi dòng ghi một kí tự xuất hiện trong xâu S và số lần xuất hiện của nó. Các kí tự đưa ra theo thứ tự chữ cái in hoa, in thường, chữ số. Các chữ cái, chữ số đưa ra theo thứ tự từ điển. 
Ví dụ:
BAI2.INP
BAI2.OUT
AzB1C9A1BC
6
A 2
B 2
C 2
z 1
1 2
9 1
Code :
const fi='bai2.inp';
 fo='bai2.out';
var dem: array['0'..'z'] of longint;
 st: string;
 res,i: longint;
 ch: char;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(st);
 for ch:='0' to 'z' do dem[ch]:=0; //O(75)
 for i:= 1 to length(st) do inc(dem[st[i]]); //O(length(st))
 res:=0;
 for ch:='0' to 'z' do //O(75)
 if dem[ch]>0 then inc(res);
 writeln(res);
 for ch:= 'A' to 'z' do //O(26)
 if dem[ch]>0 then writeln(ch,' ',dem[ch]);
 for ch:= '0' to '9' do //O(10)
 if dem[ch]>0 then writeln(ch,' ',dem[ch]);
 close(output);
END.
Ở đây chúng ta phải nhớ một số ký tự trong bảng mã ASCII để tính số lần lặp của các câu lệnh. Câu lệnh for ch:='0' to 'z' do dem[ch]:=0; nó lặp 75 lần (Vì ký tự O trong trong bảng mã là 48, ký tự z trong bảng mã là 122). Tương tự thì ta có độ phức tạp của các câu lệnh như code ở trên. Suy ra độ phức tạp của code trên là O(length(st)) = O(255).
Bài 3: (4 điểm) Hẹn gặp	
Thành phố Gloaming (Hoàng hôn) nổi tiếng với đường dẫn vào công viên thành phố. Các bức tượng tuyệt đẹp theo chủ đề thần thoại Hy lạp – La mã đặt dọc theo con đường thẳng có một sức hút không cưỡng được với mọi khách du lịch. Còn khi những tia nắng cuối cùng trong ngày miễn cưỡng rời khỏi bầu trời thì sương mù dày đặc, như một tấm voan trắng mềm mại từ từ rũ xuống. Bây giờ đứng cách quá r mét là đã không nhìn thấy mặt nhau và các bức tượng trở thành nơi lý tưởng cho các đôi nam nữ thanh niên hẹn hò. 
James Bond cần gặp gấp 2 điệp viên nội tuyến của mình để nhận các mật báo khẩn. Không muốn 2 người này nhìn thấy nhau, Bond hẹn gặp mỗi người ở một bức tượng sao cho khoảng cách giữa chúng lớn hơn r. Trên đường có n bức tượng, bức tượng thứ i ở vị trí cách đầu con đường di mét i = 1 ÷ n, 1 ≤ d1< d2 < . . .< dn ≤ 109. 
Yêu cầu: Hãy xác định James Bond có bao nhiêu cách chọn địa điểm.
Dữ liệu vào: Vào từ file văn bản BAI3.INP:
Dòng đầu tiên chứa 2 số nguyên n và r (1 ≤ n ≤ 3×105, 1 ≤ r ≤ 109).
Dòng thứ 2 chứa n số nguyên d1, d2, . . ., dn.
Kết quả: Đưa ra file văn bản BAI3.OUT một số nguyên là số cách chọn địa điểm tìm được.
Ví dụ:
BAI3.INP
BAI3.OUT
4 4
1 3 5 8
2
Rằng buộc:
Có ½ số test tương ứng với ½ số điểm có n ≤ 104
Có ½ số test tương ứng với ½ số điểm có 104 < n ≤ 3×105
Code :
const fi='bai3.inp';
 fo='bai3.out';
 maxn= 300001;
var d: array[1..maxn] of longint;
 res: int64;
 i,n,r,kq: longint;
 dau,cuoi,giua: longint;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(n,r);
 for i:= 1 to n do read(d[i]);
 res:=0;
 for i:=1 to n-1 do
 begin
 dau:=i+1; cuoi:= n; kq:=n+1;
 while dau <= cuoi do
 begin
 giua:=(dau+cuoi) div 2;
 if d[giua]- d[i]> r then
 begin
 cuoi:=giua -1;
 kq:= giua;
 end
 else dau:= giua +1;
 end;
 res:= res+n-kq+1;
 end;
 writeln(res);
 close(output);
END.
Độ phức tạp của code trên là O((n-1)log(n)) hay nói ngắn gọn hơn là O(nlog(n)).
Bài 4: (3 điểm) Tập số
Cho số tự nhiên N (1 ≤ N ≤ 106) và một tập A chỉ gồm các số tự nhiên khác nhau được xác định như sau: 
1 thuộc A.
Nếu k thuộc A thì 2k+1 và 3k+1 cũng thuộc A.
Yêu cầu: Giả sử tập A đã được sắp xếp theo thứ tự tăng dần. Hãy tìm phần tử thứ N của tập A. 
Dữ liệu vào: Vào từ file văn bản BAI4.INP gồm 1 dòng duy nhất chứa số N.
Kết quả: Ghi ra file văn bản BAI4.OUT gồm 1 số duy nhất là phần tử thứ N của tập A tìm được.
Ví dụ:
BAI4.INP
BAI4.OUT
8
15 
Rằng buộc:
Có số test tương ứng với số điểm có N ≤ 104
Có số test tương ứng với số điểm có 104 < N ≤ 106.
Code :
const fi='bai4.inp';
 fo='bai4.out';
 maxn= round(7e7); // Nghĩa là maxn = 7.107
var i,n: longint;
 a: array[1..maxn] of boolean;
 dem: longint;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(n);
 for i:= 1 to maxn do a[i]:= false;
 a[1]:= true;
 for i:=1 to maxn div 2 do
 if a[i]=true then
 begin
 if 2*i+1<= maxn then a[i*2+1]:= true;
 if 3*i+1<= maxn then a[i*3+1]:= true;
 end;
 dem:= 0;
 for i:= 1 to maxn do
 if a[i]=true then
 begin
 inc(dem);
 if dem = n then
 begin
 writeln(i);
 break;
 end;
 end;
 close(output);
END.
	Rễ dàng nhận thấy độ phức tạp của code trên là O(maxn) = O(7.107)
Bài 5: (3 điểm) Xâu con
Một xâu kí tự gọi là xâu nhị phân nếu nó chỉ chứa hai kí tự ‘0’ hoặc ‘1’.
Xâu v gọi là xâu con của xâu S nếu xâu v khác rỗng và được tạo bởi các kí tự liên tiếp trong xâu S (thứ tự giữ nguyên). Hai xâu con u và v của xâu S là khác nhau nếu nó có độ dài khác nhau hoặc được tạo từ các kí tự ở vị trí khác nhau trong xâu S. Ví dụ: xâu “010” có các xâu con là “0”, “1”, “0”, “01”, “10”, “010”.
Yêu cầu: Cho trước một xâu nhị phân S và số nguyên dương k, hãy đếm xem có bao nhiêu xâu con của xâu S chứa đúng k kí tự ‘1’.
Dữ liệu vào: Vào từ file văn bản BAI5.INP gồm:
Dòng 1 chứa một số nguyên k (0 ≤ k ≤ 106).
Dòng 2 chứa xâu nhị phân S có độ dài không quá 106.
Kết quả: Ghi ra file văn bản BAI5.OUT một số nguyên duy nhất là kết quả tìm được.
Ví dụ:
BAI5.INP
BAI5.OUT
2
01010
4
Rằng buộc:
Có số test tương ứng với số điểm có độ dài xâu nhị phân ≤ 104.
Có số test tương ứng với số điểm có 104 < độ dài xâu nhị phân ≤ 106.
Code:
const fi = 'BAI5.INP';
 fo = 'BAI5.out';
 maxn = 1000010;
var k, n, i : longint;
 st: ansistring;
 f: array[0..maxn] of longint;
 res: int64;
 left, right: longint;
procedure tinh; //O(n)
var i: longint;
begin
 f[0]:=0;
 for i:= 1 to n do
 if st[i] = '1' then f[i]:= f[i-1]+1
 else f[i]:= f[i-1];
end;
procedure timl; //O(log(n))
var dau, cuoi, giua: longint;
begin
 dau:=i; cuoi:= n; left:= -1;
 while (dau<=cuoi) do
 begin
 giua:= (dau+cuoi) div 2;
 if f[giua]-f[i-1]=k then
 begin
 left:= giua;
 cuoi:= giua -1;
 end
 else if f[giua]-f[i-1] > k then cuoi:= giua -1
 else dau:= giua +1;
 end;
end;
procedure timr; //O(log(n))
var dau, cuoi, giua: longint;
begin
 dau:=left; cuoi:= n; right:= -1;
 while (dau<=cuoi) do
 begin
 giua:= (dau+cuoi) div 2;
 if f[giua]-f[i-1]=k then
 begin
 right:= giua;
 dau:= giua +1;
 end
 else if f[giua]-f[i-1] > k then cuoi:= giua -1
 else dau:= giua +1;
 end;
end;
BEGIN
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(k);
 readln(st);
 n:= length(st);
 tinh;
 res:=0;
 for i:=1 to n do //O(n)
 begin
 timl; //O(log(n))
 if left-1 then //O(1)
 begin
 timr; //O(log(n))
 res:= res+ right-left+1; //O(1)
 end;
 end;
 writeln(res);
 close(output);
END.
Độ phức tạp của thủ tục procedure tinh; là O(n), của procedure timl; là O(log(n)), của procedure timr; là O(log(n)). Suy ra độ phức tạp của cả chương trình là O(nlog(n)).
C. PHẦN KẾT LUẬN
Đánh giá độ phức tạp của thuật toán là công việc hết sức quan trọng trong các kỳ thi học sinh giỏi môn Tin học. Vì vậy khi đọc đề bài chúng ta phải biết bài đó phải làm với độ phức tạp bao nhiêu thì được điểm tối đa. Qua cách trình bày ở trên, có thể giúp giáo viên và học sinh hiểu rễ dàng hơn về cách đánh giá độ phức tạp của thuật toán.
Đề tài này đã mang tính thực tiễn rất cao, cụ thể là: giúp giáo viên và học sinh khi làm bài tập thì biết được độ phức tạp của bài mình làm.
Tài liệu tham khảo
[1] 	Tài liệu giáo khoa chuyên tin quyển 1, Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Hùng, NXB Giáo dục, năm 2009.
[2] 	Đề thi chọn học sinh giỏi môn Tin học tỉnh Thanh hóa, SGD&ĐT Thanh Hóa, năm 2017.
XÁC NHẬN CỦA THỦ
TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 13 tháng 6 năm 2017
Tôi xin cam đoan đây là SKKN của mình viết, không sao chép nội dung của người khác.
(Ký và ghi rõ họ tên)
Nguyễn Đặng Phú