10 Tin 2k11 Home

Mã đi tuần (hay hành trình của quân mã)

Angle_Bup — Tue, 04 Oct 2011 09:15:27 GMT

Mã đi tuần (hay hành trình của quân mã) là bài toán về việc di chuyển một quân mã trên bàn cờ vua ( 8 x 8). Quân mã được đặt ở một ô trên một bàn cờ trống nó phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần.

Lời giải bài toán trên bàn cờ 5x5

Một hành trình của quân mã trên bàn cờ

Có rất nhiều lời giải cho bài toán này, chính xác là 26.534.728.821.064 lời giải trong đó quân mã có thể kết thúc tại chính ô mà nó khởi đầu.

Một hành trình như vật được gọi là hành trình đóng. Có những hành trình, trong đó quân mã sau khi đi hết tất cả 64 ô của bàn cờ (kể cả ô xuất phát), thì từ ô cuối của hành trình không thể đi về ô xuất phát chỉ bằng một nước đi. Những hành trình như vậy được gọi là hành trình mở.

Nhiều biến thể của chủ đề này được các nhà toán học nghiên cứu, trong đó có nhà toán học Euler. Các biến đổi có thể theo các hướng:

thay đổi kích thước bàn cờ
biến thành trò chơi hai người theo tư tưởng này
giảm nhẹ các yêu cầu trên đường đi của quân mã.

Bài toán mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm đường đi Hamilton trong l‎ý thuyết đồ thị, là một bài toán NP-đầy đủ. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm chu trình hamiltonian.

Hành trình của quân mã trên nửa bàn cờ đã được giới thiệu dưới dạng thơ trong một tác phẩm tiếng Phạn.

Giải thuật đầu tiên đầy đủ cho bài toán về hành trình của quân mã là Giải thuật Warnsdorff, công bố lần đầu năm 1823 bởi H. C. Warnsdorff.

Hai lời giải với bàn cờ 8 x 8

(theo Bách khoa toàn thư mở Wikipedia)

Ý tưởng cơ bản: dùng thuật toán quay lui; xuất phát từ 1 ô, gọi số nước đi là t=1, ta cho quân mã thử đi tiếp 1 ô (có 8 nước đi có thể), nếu ô đi tiếp này chưa đi qua thì chọn làm bước đi tiếp theo. Tại mỗi nước đi kiểm tra xem tổng số nước đi bằng n*n chưa, nếu bằng thì mã đã đi qua tất cả các ô ⇒ dừng (do chỉ cần tìm một giải pháp). Trường hợp ngược lại, gọi đệ quy để chọn nước đi tiếp theo. Ngoài ra, nếu tại một bước tìm đường đi, nếu không tìm được đường đi tiếp thì thuật toán sẽ quay lui lại nước đi trước và tìm đường đi khác…

Cấu trúc dữ liệu:

Mảng board[MAX][MAX]: lưu bàn cờ, trong đó board[i][j] là ô (i, j); giá trị của board[i][j] là 0 khi quân mã chưa đi qua, và >0 khi quân mã đã đi qua, giá trị board[i][j] lúc này chính là thứ tự nước đi trên hành trình.
Mảng dr[8], dc[8]: lưu các độ dời của bước đi kế tiếp, có tám nước đi có thể cho vị trí quân mã hiện tại. Do đó để đi nước thứ i ta chỉ cần cộng thêm dr[i] cho dòng và dc[i] cho cột!.
dr[] = {-2, -2, -1, -1, 1, 1, 2, 2} dc[] = {-1, 1, -2, 2, -2, 2, -1, 1}

: Thứ tự tám nước đi theo chiều kim đồng hồ

Thuật giải đệ quy:

Tại mỗi bước lần lượt cho quân mã thử tất cả các nước đi kế tiếp (tám nước đi kế tiếp). Với mỗi bước đi, kiểm tra xem nếu nước đi hợp lệ (chưa đi qua và ở trong bàn cờ) thì thử đi nước này. Nếu quân mã đã đi qua hết bàn cờ thì xuất kết quả. Ngược lại thì gọi đệ quy tiếp cho vị trí mới thử trên. Lưu ý là mỗi khi vị trí đã đi qua được đánh dấu chính bằng chính thứ tự nước đi trên bàn cờ. Sau khi không thử vị trí này thì phải bỏ đánh dấu để chọn giải pháp khác (trường hợp quay lui).
Nếu coi các ô của bàn cờ là các đỉnh của đồ thị và các cạnh là nối giữa hai đỉnh tương ứng với hai ô mã giao chân thì dễ thấy rằng hành trình của quân mã cần tìm sẽ là một đường đi Hamilton. Ta có thể xây dựng hành trình bằng thuật toán quay lui kết hợp với phương pháp duyệt ưu tiên Warnsdorff: Nếu gọi deg(x, y) là số ô kề với ô (x, y) và chưa đi qua (kề ở đây theo nghĩa đỉnh kề chứ không phải là ô kề cạnh) thì từ một ô ta sẽ không thử xét lần lượt các hướng đi có thể, mà ta sẽ ưu tiên thử hướng đi tới ô có deg nhỏ nhất trước. Trong trường hợp có tồn tại đường đi, phương pháp này hoạt động với tốc độ tuyệt vời: Với mọi n chẵn trong khoảng từ 6 tới 18, với mọi vị trí ô xuất phát, trung bình thời gian tính từ lúc bắt đầu tới lúc tìm ra một nghiệm < 1 giây. Tuy nhiên trong trường hợp n lẻ, có lúc không tồn tại đường đi, do phải duyệt hết mọi khả năng nên thời gian thực thi lại hết sức tồi tệ. (Có xét ưu tiên như trên hay xét thứ tự như trước kia thì cũng vậy thôi)

(nguồn: kythuatlaptrinh)

Kiểu bản ghi

Angle_Bup — Mon, 03 Oct 2011 14:46:01 GMT

Khái niệm

Các phần trình bày trước cho thấy ngôn ngữ Pascal rất mạnh trong việc giải quyết các bài toán thiên về tính toán. Trong phần này chúng ta sẽ thấy thêm một khả năng mạnh mẽ nữa của ngôn ngữ Pascal trong lĩnh vực quản lý: quản lý nhân sự, quản lý vật tư, quản lý tài chánh,.v.v.

Hàng ngày chúng ta rất quen thuộc với một danh sách sinh viên như dưới đây:

Mỗi dòng liệt kê các dữ liệu về một người, mỗi cột là một dữ liệu thành phần cung cấp thông tin về một thuộc tính cụ thể của những người đó.

Trong ngôn ngữ Pascal, mỗi dòng được gọi là một RECORD (dịch là bản ghi hay thẻ ghi), mỗi cột là một FIELD (dịch là trường hay thành phần, hay thuộc tính cho sát với thực tế).

Nói tổng quát, mỗi bản ghi là một tập gồm nhiều trường (field), các trường có thể có kiểu dữ liệu khác nhau.

14.1.2. Mô tả bản ghi :

Kiểu bản ghi được mô tả bằng cách dùng từ khóa RECORD kèm theo một danh sách khai báo các tên trường và kiểu dữ liệu tương ứng, kết thúc bằng từ khóa END; , tức là:

TYPE

Tênkiểu = RECORD

Têntrường1 : Kiểudliệu1;

Têntrường2 : Kiểudliệu2;

...

Têntrườngk : Kiểudliệuk;

End;

Ví dụ 1: Ta định nghĩa một kiểu KSVIEN như sau:

TYPE

KSVIEN = RECORD

Hoten:String[20];

Maso : String[8];

Toan, Ly, DTB: Real;

End;

Theo mô tả trên, ta có một kiểu dữ liệu mới đặt tên là KSVIEN có cấu trúc bản ghi gồm 5 trường (thuộc tính) là:

Ví dụ 2:

Ta mô tả thời gian là kiểu KDATE có ba trường ngày , tháng, năm như sau:

TYPE

KDATE = RECORD

Ngay : 1..31;

Thang : 1..12;

Nam : Integer;

End;

Ví dụ 3:

Ðể quản lý các sách trong một thư viện, ta xây dựng một kiểu bản ghi KSACH như sau:

TYPE

KSACH = RECORD

Ma_so_sach: String[6];

Ten_doc_gia: String[20];

Nam_xban :Integer;

Gia_tien: Real;

Ngay_muon : KDATE;

End;

Kiểu KSACH là một bản ghi có 5 trường mô tả 5 thuộc tính của sách là: mã số sách, tên độc giả, năm xuất bản, gía tiền và ngày mượn.

Ví dụ này cho thấy các bản ghi có thể được mô tả lồng nhau: kiểu dữ liệu của một trường của bản ghi này lại có thể là một kiểu bản ghi khác đã được định nghĩa trước đó. Trong bản ghi KSACH, Ngay_muon là một trường có kiểu dữ liệu là một bản ghi kiểu KDATE.

Mỗi đối tượng cần quản lý có thể có nhiều trường, song tùy yêu cầu quản lý mà ta chỉ lựa chọn và khai báo những trường thật sự cần thiết. Khai báo thừa thì hao phí bộ nhớ, nhưng nếu thiếu thì công tác quản lý sẽ khó khăn do thiếu thông tin. Vì vậy, nên khai báo các trường với số lượng ít nhất nhưng đủ dùng.

14.1.3. Sử dụng bản ghi :

Kiểu bản ghi sau khi đã được định nghĩa có thể dùng khai báo cho các biến. Ví dụ :

Var

X, Y, Z : KSVIEN;

Trong đó KSVIEN là bản ghi đã mô tả ở phần trên.

Theo khai báo này, X ,Y và Z là ba biến kiểu bản ghi KSVIEN, mỗi biến đều có 5 trường Hoten, Maso, Toan, Ly và DTB.

Ðể thâm nhập vào một trường của bản ghi ta viết tên biến kiểu bản ghi, sau đó là dấu chấm ‘.’ và tên trường, tức là :

Tênbiến .Têntrường

Các lệnh dưới đây gán gía trị cho từng trường của biến X :

X.Hoten :=‘Nguyen Van An’;

X.Maso :=‘1973208’;

X.Toan :=8.0;

X.Ly :=7.0;

X.DTB :=(X.Toan+X.Ly)/2;

Ðể nhập dữ liệu cho trường Hoten của biến Y, ta viết:

Write(‘Nhap ho ten sinh vien Y : ‘);

Readln(Y.Hoten);

Sở dĩ phải viết tên biến bản ghi ở trước tên trường là để xác định trường đó là của biến bản ghi nào. Mỗi biến X, Y, Z đều có trường Hoten, nên nếu chỉ viết Hoten thôi thì không biết đó là Hoten của ai: X, Y hay Z ?. Còn viết X.Hoten là chỉ rõ đây là Hoten của biến X.

Như vậy, mỗi trường của biến bản ghi có thể thâm nhập và sử dụng như một biến bình thường. X.Hoten là biến kiểu String[20], X.Maso là biến kiểu String[8], ..., X.DTB là biến kiểu Real.

Ðối với các bản ghi lồng nhau, cách truy xuất đến từng trường cũng tương tự.

Ví dụ: Cho khai báo biến S kiểu KSACH:

Var

S : KSACH ;

Ðể truy nhập đến các trường Ngay, Thang, Nam của Ngay_muon ta viết :

S.Ngay_muon.Têntrường

Chẳng hạn gán :

S.Ngay_muon.Ngay := 2;

S.Ngay_muon.Thang := 9;

S.Ngay_muon.Nam := 1999;

Hai biến bản ghi cùng kiểu có thể gán cho nhau. Lệnh :

Y:=X;

gán gía trị của từng trường của biến X cho trường tương ứng của biến Y. Vậy lệnh trên tương đương với khối 5 lệnh sau :

begin

Y.Hoten :=X.Hoten;

Y.Maso :=X.Maso;

Y.Toan :=X.Toan;

Y.Ly :=X.Ly;

Y.DTB :=X.DTB;

end;

Các bản ghi có thể so sánh bằng nhau hoặc khác nhau:

Ví dụ:

If X=Y then writeln(‘ X và Y là một người ‘);

If X<>Y then writeln(‘ X khác Y ‘);

Tuy nhiên không có phép so sánh <, <=, >, >= cho các bản ghi.

Hai bản ghi có thể hoán đổi gía trị cho nhau theo nghĩa hoán đổi từng cặp gía trị của các trường tương ứng.

Giống như các biến đơn giản, để hoán đổi hai bản ghi X và Y ta dùng ba lệnh:

Z:=X; X:=Y; Y:=Z;

trong đó Z là biến trung gian cùng kiểu bản ghi với X và Y.

Ví dụ: Nếu biến X và Y có các trường tương ứng là :

X.Hoten =‘Nguyen Van An’

X.Maso =‘1973208’

X.Toan =8.0

X.Ly =7.0

X.DTB =7.5

Y.Hoten =‘Tran Thi Nga’

Y.Maso =‘1974564’

Y.Toan =5.0

Y.Ly =8.0

Y.DTB =6.5

thì sau khi hoán đổi, ta được :

X.Hoten =‘Tran Thi Nga’

X.Maso =‘1974564’

X.Toan =5.0

X.Ly =8.0

X.DTB =6.5

Y.Hoten =‘Nguyen Van An’

Y.Maso =‘1973208’

Y.Toan =8.0

Y.Ly =7.0

Y.DTB =7.5

14.1.4. Câu lệnh WITH :

Khi làm việc với nhiều trường của một biến bản ghi thì cách thâm nhập ở trên tỏ ra rườm rà vì phải viết nhiều lần tên biến trước tên trường.

Ðể đơn giản cách viết, Pascal đưa ra câu lệnh :

WITH Tênbiến DO LệnhP;

Tên biến thuộc kiểu bản ghi.

Nếu LệnhP có truy xuất đến các trường của Tên biến thì không cần phải viết Tên biến và dấu chấm trước các tên trường.

Ví dụ, thay vì viết:

X.Hoten:= ‘Nguyen Van An’;

ta có thể viết :

WITH X DO Hoten:= ‘Nguyen Van An’;

Ðể in các trường của biến X lên màn hình, ta viết:

WITH X DO
Begin

Writeln(‘ Họ và tên :’ , Hoten);

Writeln(‘ Mã số sinh viên :’ , Maso);

Writeln(‘ Ðiểm Toán :’ , Toan: 4:1);

Writeln(‘ Ðiểm Lý :’ , Ly: 4:1);

Writeln(‘ Ðiểm trung bình : ‘ , DTB :4:1);

End;

Tất cả các tên trường nằm trong khối begin và end được hiểu là các trường của biến X (nếu không ghi rõ tên biến nào khác).

Các lệnh sau gán các gía trị cho các trường của biến S kiểu KSACH là một bản ghi lồng nhau:

WITH S DO

begin

Ma_so_sach:=‘TH-435’;

Ten_doc_gia:=‘Nguyen van Mai’;

Nam_xban :=1999;

Gia_tien:= 15000;

WITH Ngay_muon DO

begin

Ngay:=2;

Thang:=9;

Nam:=1999;

end;

14.1.5. Mảng các bản ghi :

Trong thực tế, ta thường phải quản lý một danh sách sinh viên của một lớp, một danh sách các quyển sách trong thư viện. Ví thế mảng các bản ghi được dùng rất phổ biến.

Khi khai báo :

VAR

DS : Array[1..50] of KSVIEN;

hoặc :

TYPE

KMang = Array[1..50] of KSVIEN;

VAR

DS: KMang;

thì ta có một mảng DS gồm 50 phần tử DS[1],..., DS[50] cùng kiểu bản ghi KSVIEN. Mỗi DS[i], i=1,..., 50 là một bản ghi có 5 trường Hoten, Maso, Toan, Ly, DTB lưu trữ các thông tin về sinh viên thứ i trong danh sách.

Ðể nhập dữ liệu ( Hoten, Maso, Toan, Ly ) rồi tính Ðiểm trung bình cho 50 sinh viên này, ta dùng vòng lặp For phối hợp với câu lệnh WITH :

For i:=1 to 50 do

WITH DS[i] DO

begin

Write(‘Nhap ho ten sinh vien thu ‘,i,’ : ‘); Readln(Hoten);

Write(‘Nhap ma so sinh vien thu ‘,i,’ : ‘); Readln(Maso);

Write(‘Nhap điểm Toan, Ly sinh vien thu ‘,i,’ : ‘);

Readln(Toan, Ly);

DTB:=(Toan + Ly)/2;

end;

Ðể sắp xếp danh sách sinh viên theo trật tự giảm của DTB sao cho người có DTB cao thì đứng trước, người có DTB thấp thì đứng sau, ta có thể áp dụng phương pháp sắp xếp mảng, song chỉ lấy trường DTB làm tiêu chuẩn so sánh:

For i:=1 to 49 do

For j:=i+1 to 50 do

If DS[i].DTB < DS[j].DTB then

begin { Ðổi chỗ DS[i] và DS[j] }

Z:=DS[i];

DS[i]:=DS[j];

DS[j]:=Z;

end;

Ở đây Z là biến bản ghi cùng kiểu với các phần tử DS[i].

Khi sắp xếp theo DTB tăng hoặc giảm thì trường DTB được gọi là "khóa" ( key) sắp xếp.

Một cách tương tự, có thể sắp xếp danh sách sinh viên theo khóa là điểm Toan, hoặc điểm Ly, hoặc Maso, hoặc theo Hoten.

Ðể in danh sách đã sắp xếp lên màn hình, ta dùng lệnh :

For i:=1 to 50 do WITH DS[i] DO

Writeln( i:2, Hoten:25, Maso:9 , Toan:5:1, Ly:5:1, DTB:5:1);

(nguồn: http://www.uit.edu.vn/

)

Đệ Quy

Angle_Bup — Mon, 03 Oct 2011 14:41:58 GMT

Thuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái niệm thuật toán. Như đã biết, một thuật toán cần phải thỏa mãn 3 tính chất :

– Tính hữu hạn.
– Tính xác định
– Tính đúng đắn

Tuy nhiên, có những bài toán mà việc xây dựng một thuật toán với đầy đủ ba tính chất trên rất khó khăn. Trong khi đó, nếu ta xây dựng một thuật toán vi phạm một vài tính chất trên thì cách giải lại trở nên đơn giản hơn nhiều và có thể chấp nhận được. Một trong những trường hợp đó là thuật toán đệ quy.

Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (hay nói một cách nôm na là đồng dạng) nhưng ở cấp độ thấp hơn (chẳng hạn : độ lớn dữ liệu nhập nhỏ hơn, giá trị cần tính toán nhỏ hơn, ....), và quá trình này tiếp tục cho đến lúc bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ kết quả ở cấp độ này, ta sẽ lần ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc giải được bài toán ở cấp độ ban đầu.

Trong toán học ta cũng thường gặp những định nghĩa về những đối tượng, những khái niệm dựa trên chính những đối tượng, khái niệm đó.

Ðịnh nghĩa giai thừa

Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là :
0! = 1
n! = (n-1)!n với mọi n>0

Ðịnh nghĩa dãy số Fibonacci

f₀ = 1
f₁ = 1
f_n = f_n-1 + f_n-2 với mọi n>1

Theo toán học, những khái niệm được định nghĩa như vậy gọi là định nghĩa theo kiểu quy nạp. Chính vì vậy, đệ quy có sự liên hệ rất chặt chẽ với quy nạp toán học.

Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ bằng một số hữu hạn các mệnh đề. Tuy nhiên, đặc tính này của đệ quy lại vi phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong thuật toán phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với thuật toán đệ quy, bước thứ n không được xác định ngay trong ngữ cảnh của nó mà phải xác định thông qua một bước thấp hơn. Chẳng hạn, để tính được giá trị phần tử thứ 5 của dãy Fibonacci theo định nghĩa ở trên, ta phải tính f₃+f₄, nhưng ta chưa biết giá trị f₃ và f₄ tại thời điểm này. Ðến đây, ta phải lùi lại để tính f₃ và f₄. Ðể tính f₃ ta lại phải lùi về để tính f₂,...Tất nhiên, là quá trình tính lùi này phải dừng sau một số hữu hạn bước. Trong trường hợp này, điểm dừng chính là giá trị f₁ và f₀.

Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại một số trường hợp đặc biệt nào đó, còn gọi là trường hợp dừng. Sau đó, các trường hợp khác của bài toán sẽ được xác định thông qua trường hợp đặc biệt này. Ðối với việc tính dãy Fibonacci, trường hợp dừng chính là giá trị của f₀ và f₁.

Nói một cách chính xác, mọi thuật toán đệ quy đều gồm hai phần:

Phần cơ sở
Là các trường hợp không cần thực hiện lại thuật toán (hay không có yêu cầu gọi đệ quy). Nếu thuật toán đệ quy không có phần này thì sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý do này mà người ta đôi lúc còn gọi phần cơ sở là trường hợp dừng.
Phần đệ quy
Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán nhưng với một cấp độ dữ liệu thấp hơn.

Thuật toán - Cách đánh giá thuật toán

Angle_Bup — Wed, 31 Aug 2011 04:29:56 GMT

tuần đầu tiên!

Angle_Bup — Sat, 27 Aug 2011 13:03:17 GMT

^^ sau một tuần đi học thì cảm giác thế nào rồi các mem 11Tin???

Demo sắp xếp tuần tự

Angle_Bup — Wed, 24 Aug 2011 07:24:04 GMT

/DEMO_INTERCHANGE_SORT.exe

Lý Thuyết Đồ Thị

Angle_Bup — Tue, 23 Aug 2011 07:35:34 GMT

Lý Thuyết Đồ Thị của thầy Vinh nhé!

Free Pascal

Angle_Bup — Sun, 21 Aug 2011 14:41:42 GMT

Các em chưa có Free Pascal thì down về nhé!

Download Free Pascal 2.4

Nếu không down được thì vào trang này down về cũng được

http://www.freepascal.org/down/i386/win32-ftp.freepascal.org.var

Chú ý chú ý! Thời khóa biểu (Update)

Angle_Bup — Sat, 20 Aug 2011 03:36:23 GMT

thời khóa biểu năm học 2011-2012 của lớp ta

Download

còn thời khóa biểu buổi chiều thì sáng t2 thầy Hồng phổ biến sau nhé.

Dưới đây là tkb và môn cụ thể mà thầy có thể nhớ được

Thứ	TIN	Môn
2	Chào cờ
	QUÍ HIỆP	Tin
	QUÍ HIỆP	Tin
	HÀ NAM	V.Lý
	THU VÂN	GDCD
3	Đức Thủy	Sủ
	DUNG	Địa
	THOA	Toán
	THOA	Toán
	o	o
4	NG..DIỆP	Văn
	NG..DIỆP	Văn
	CẨM V ÂN	Anh
	CẨM V ÂN	Anh
	TRÚC	Sinh
5	THOA-TOÁN	Toán
	THOA-TOÁN	Toán
	TRANG-H	Hóa
	TRANG-H	Hóa
	DUNG-Đ?A	Đ?a
6	NG..Diệp	Văn
	HÀ NAM	V.Lý
	HÀ NAM	V.Lý
	CẨM V ÂN	Anh
	TRANG-H	Hóa
7	HOÀNG ANH	Tin
	HOÀNG ANH	Tin
	Khanh	Công Nghệ
	H..ANH-NG
	Sinh Hoạt

ÐỘ PHỨC TẠP CỦA THUẬT TOÁN

Angle_Bup — Fri, 19 Aug 2011 09:06:15 GMT

II. ÐỘ PHỨC TẠP CỦA THUẬT TOÁN

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

        Một chương trình máy tính thường được cài đặt dựa trên một thuật toán để giải bài toán hay vấn đề đặt ra. Một đòi hỏi đương nhiên là thuật toán phải đúng. Tuy nhiên, ngay cả khi thuật toán đúng, chương trình vẫn có thể là không sử dụng được đối với một số dữ liệu nhập nào đó bởi vì thời gian cần thiết để chạy chương trình hay vùng nhớ cần thiết để lưu trữ dữ liệu (như các biến trong chương trình, các file lưu trữ, ...) quá lớn.
        Thuật ngữ phân tích thuật toán đề cập đến một quá trình tìm ra một đánh giá về thời gian và không gian cần thiết để thực hiện thuật toán. Ðộ phức tạp của thuật toán được thể hiện qua khối lượng thời gian và không gian để thực hiện thuật toán. Không gian ở đây được hiểu là các yêu cầu về bộ nhớ, thiết bị lưu trữ, … của máy tính để thuật toán có thể làm việc được. Việc xem xét độ phức tạp về không gian của thuật toán phụ thuộc phần lớn vào cấu trúc dữ liệu được sử dụng trong cài đặt thuật toán. Trong phần này chúng ta chỉ đề cập đến độ phức tạp về thời gian của thuật toán.
        Chúng ta cũng có thể đạt được những thông tin rất hữu ích khi phân tích độ phức tạp thời gian của thuật toán cơ sở của một chương trình máy tính. Ðánh giá một cách chính xác thời gian thực hiện một chương trình phụ thuộc vào rất nhiều yếu tố và là một công việc rất khó khăn. Tuy nhiên các nhà toán học đã phân tích cho chúng ta hầu độ phức tạp của hầu hết các thuật toán thường được sử dụng như các thuật toán sắp xếp, các thuật toán tìm kiếm, các thuật toán số học, v.v…
        Ðộ phức tạp thời gian của thuật toán thường được đánh giá dựa vào số lượng thao tác được sử dụng trong thuật toán và số lượng thao tác này phụ thuộc vào cở (size) của dữ liệu nhập. Ta còn gọi độ phức tạp thời gian của thuật toán là độ phức tạp tính toán. Các thao tác được sử dụng để đo độ phức tạp của thuật toán có thể là phép so sánh 2 số nguyên, cộng 2 số nguyên, nhân 2 số nguyên, chia 2 số nguyên, hay bất kỳ thao tác cơ bản nào khác. Như thế ta có thể xem thời gian thực hiện thuật toán là một hàm phụ thuộc vào dữ liệu nhập (thường là cở của dữ liệu nhập). Nếu gọi cở dữ liệu nhập là n thì độ phức tạp có thể được xem là một hàm theo n.
        Chúng ta có thể đặt ra câu hỏi về thời gian thực hiện thuật toán nhỏ nhất đối với các dữ liệu nhập có cở n. Ta có thể nêu lên một số bài toán có dữ liệu nhập có cở n như: sắp xếp dãy n số nguyên, tìm số nhỏ nhất trong dãy n số nguyên, v.v.... Thời gian nhỏ nhất này được gọi là thời gian thực hiện thuật toán trong trường hợp tốt nhất đối với dữ liệu nhập có cở n. Tương tự ta cũng thường đề cập đến thời gian thực hiện thuật toán lớn nhất đối với các dữ liệu nhập có cở n, và gọi là thời gian thực hiện thuật toán trong trường hợp xấu nhất đối với dữ liệu nhập có cở n. Ngoài ra, đối với thuật toán có dữ liệu nhập có cở n trong một tập hữu hạn nào đó, ta còn muốn tính ra thời gian trung bình để thực hiện thuật toán.
Ví dụ 1: Thuật toán tìm giá trị lớn nhất trong dãy gồm n số nguyên (xem ví dụ 1, mục I). Trong thuật toán này nếu ta xem thời gian thực hiện thuật toán là số lần thực hiện phép so sánh hay phép gán thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là:

t(n) = 1 + 2*(n-1) = 2n+1

và thời gian thực hiện thuật toán trong trường hợp tốt nhất là:
T(n) = 1 + (n-1) = n.

2.2 Ký hiệu O

        Việc tính toán độ phức tạp (về thời gian hay về tính toán) của thuật toán sẽ giúp ta có thể đánh giá và so sánh các thuật toán. Tuy nhiên có những trường hợp mà 2 thuật toán khác nhau để giải quyết cùng một bài toán có số lượng thao tác cơ bản là f(n) và g(n), với n là cở dữ liệu nhập, rất khó so sánh đánh giá hơn kém theo sự so sánh lớn bé thông thường. Hơn nữa trong hầu hết các thuật toán như thuật toán sắp xếp, thuật toán tìm kiếm, … ta không thể tính ra được số lượng thao tác f(n) theo n.
        Thông thường ta ít chú ý tới con số chính xác về thời gian thực hiện thuật toán trong trường hợp xấu nhất và trong trường hợp tốt nhất. Ðiều mà chúng ta thường quan tâm hơn khi đánh giá độ phức tạp thời gian của thuật toán là mức độ tăng lên của thời gian thực hiện thuật toán khi cở của dữ liệu nhập tăng lên. Chẳng hạn, một thuật toán đang được xem xét nào đó có thời gian thực hiện trong trường hợp xấu nhất và trong trường hợp tốt nhất lần lượt là:
t(n) = 20n² + 5n + 1,
T(n) = n² + 10n + 1.
        Như thế, nếu như n rất lớn thì ta có thể xấp xỉ t(n) và T(n) với 20n² và n². Có thể nói rằng t(n) và T(n) tăng giống như n² khi n tăng. Ðể diễn đạt điều này, người ta định nghĩa và sử dụng ký hiệu O được định nghĩa như dưới đây.
Ðịnh nghĩa: Cho 2 hàm thực f và g có miền xác định trong tập số tự nhiên N. Ta viết:
f(n) Î O(g(n))
và nói là f(n) có cấp cao nhất là g(n), hay f(n) thuộc lớp O(g(n)), khi có một hằng số dương C sao cho:
| f(n)|  ≤ C . | g(n) |,
với "hầu hết" n thuộc miền xác định của các hàm f và g. Từ "hầu hết" ở đây ý nói là "với mọi chỉ trừ một số hữu hạn", hay nói một cách chính xác là
$ C > 0, $ k Î N, " n Î N, n ≥ k ® | f(n)| ≤ C . | g(n) |
Ví dụ:
Với t(n) = 20n² + 5n + 1 và T(n) = n² + 10n + 1. Ta có thể chứng minh được rằng nói t(n) và T(n) có cấp cao nhất là n², tức là t(n) Î O(n²) và T(n) Î O(n²).
Xét f(n) = log (n!). Ta có
n! = 1.2. . .n ≤ n.n. . .n ≤ nⁿ
Þ log(n!) ≤ log (nⁿ) = n.log(n)
Suy ra
            log(n!) Î O(n log n)
Ðịnh lý II.1: Nếu f(n) là một đa thức bậc k theo n, tức là f(n) có dạng
f(n) = a_kn^k + a_k-1n^k-1 + . . . + a₁n + a₀, với a_k≠ 0,

thì ta có f(n) thuộc lớp O(n^k).
Ngoài ra ta còn có các tính chất sau đây:
Giả sử rằng f₁(n) Î O(g₁(n)) và f₂(n) Î O(g₂(n)). Khi ấy ta có
f₁(n) + f₂(n) Î O ( max(g₁(n), g₂(n)) )
Hệ quả là nếu f₁(n) và f₂(n) đều thuộc O(g(n)) thì ta cũng có
f₁(n) + f₂(n) Î O(g(n))
Giả sử rằng f₁(n) Î O(g₁(n)) và f₂(n) Î O(g₂(n)). Khi ấy ta có
f₁(n).f₂(n) Î O ( g₁(n).g₂(n) )
Ví dụ 2: Ðánh giá độ phức tạp (thời gian) của thuật toán tìm kiếm tuyến tính (xem ví dụ 3 ở mục I)
Ðối với thuật toán này, trong trường hợp tốt nhất (phần tử cần tìm nằm ngay tại vị trí đầu tiên của dãy) thời gian thực hiện thuật toán là 1. Ta viết thời gian thực hiện thuật toán trong trường hợp tốt nhất là: O(1).
Ta cũng có thể tính toán ra được thời gian thực hiện thuật toán trong trường hợp xấu nhất và thời gian thực hiện thuật toán trung bình đều là O(n).

2.3 Một số lớp độ phức tạp

Liên quan đến độ phức tạp của thuật toán ta có một số thuật ngữ thường dùng trong sự phân lớp các độ phức tạp của thuật toán được liệt kê dưới đây:
độ phức tạp hằng: O(1).
độ phức tạp logarith: O(log n).
độ phức tạp tuyến tính: O(n).
độ phức tạp n log n: O(n log n).
độ phức tạp đa thức: O(n^b).
độ phức tạp mũ: O(bⁿ), trong đó b > 1.
độ phức tạp giai thừa: O(n!).