Bài giảng Cấu trúc dữ liệu và giải thuật - Chương I: Tổng quan về giải thuật và cấu trúc dữ liệu

Cấu trúc dữ liệu và giải thuật  (Data structure and Algorithms) 
Nội dung chương trình 
Chương I 
	 TỔNG QUAN VỀ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU 
Khái niệm về cấu trúc dữ liệu và giải thuật 
Một số cú pháp điều khiển 
Đánh giá độ phức tạp của giải thuật 
Chương II. 
	TÌM KIẾM VÀ SẮP XẾP 
I. Các giải thuật tìm kiếm nội 
Tìm kiếm tuyến tính 
Tìm kiếm nhị phân 
II. Các giải thuật sắp xếp nội 
Chọn trực tiếp (Selection sort) 
Chèn trực tiếp (Insertion sort) 
Đổi chỗ trực tiếp (Interchange Sort) 
Nổi bọt ( Buble sort) 
Sắp xếp cây (Heap sort) 
Sắp xếp dựa trên phân hoạch (Quick sort) 
Sắp xếp trộn trực tiếp (Merge sort ) 
Nội dung chương trình 
Chương III. 
	CẤU TRÚC DỮ LIỆU ĐỘNG 
Kiểu dữ liệu con trỏ 
Danh sách liên kết-khái niệm 
Danh sách liên kết đơn 
Tổ chức danh sách đơn 
Các thao tác cơ bản trên danh sách đơn 
Tạo danh sách 
Duyệt danh sách 
Chèn phần tử vào danh sách 
Xoá phần tử khỏi danh sách 
3. Sắp xếp dánh sách ( lý thuyết+đọc thêm ) 
4. Các cấu trúc đặc biệt của danh sách đơn 
Stack 
Queue 
IV. Một số cấu trúc dữ liệu dạng danh sách liên kết khác 
Danh sách liên kết kép 
Hàng đợi 2 đầu 
Danh sách liên kết có thứ tự 
Danh sách liên kết vòng 
Danh sách có nhiều mối liên kết 
Nội dung chương trình 
Chương IV. 
	 CẤU TRÚC CÂY 
Khái niệm về cây 
Cây nhị phân 
Một số tính chất của cây nhị phân 
Biểu diễn cây nhị phân 
Duyệt cây nhị phân 
Biểu diễn cây tổng quát 
III. Cây nhị phân tìm kiếm 
Tìm một phần tử 
Thêm một phần tử 
Huỷ một phần tử 
IV. Cây nhị phân cân bằng 
Cây nhị phân cân bằng hoàn toàn 
Cây nhị phân cân bằng 
Nội dung chương trình 
Phần II. 
Bài tập+Thực hành + Ceminar 
- Cài đặt các chương thuật toán trong phần lý thuyết đã học 
Nội dung chương trình 
Tài liệu tham khảo 
Trần Hạnh Nhi-Dương Anh Đức , Giáo trình cấu trúc dữ liệu và giải thuật ĐH Quốc gia Tp Hồ Chí Minh 
Đỗ Xuân Lôi , Cấu trúc dữ liệu và giải thuật , NXB Khoa học kỹ thuật , 1996 
Robert Sedgewick , Cẩm nang thuật toán , tập 1, NXB Khoa học kỹ thuật , 1994, bản dịch của nhóm tác giả ĐH TH Tp . HCM 
N. Wirth: Algorithms+Data structures=Programs (Prentice Hall, 1976) 
V v 
Tổng quan về các giải thuật và cấu trúc dữ liệu 
Chương I 
Khái niệm về cấu trúc dữ liệu và giải thuật 
Một số cú pháp điều khiển 
Đánh giá độ phức tạp của giải thuật 
I. Khái niệm về cấu trúc dữ liệu và giải thuật 
Trong phạm vi tin học , ta có thể quan niệm bài toán (Problems) là công việc mà ta muốn máy tính thực hiện 
1. Khái niệm bài toán 
VD : In dòng chữ ra màn hình , giải phương trình bậc 2, quản lý cán bộ trong một cơ quan  
* Diễn đạt bài toán thành 2 thành phần 
Input: Thông tin đầu vào 
Output: Thông tin đầu ra 
Ví dụ 
Giải thuật ( thuật toán -Algorithm): là một dãy hữu hạn các thao tác chặt chẽ và rõ ràng đượ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 đó , ta nhận được mục tiêu định trước 
2. Khái niệm Cấu trúc dữ liệu và giải thuật 
Cấu trúc dữ liệu : là tập các dữ liệu có quan hệ với nhau , được tổ chức theo những phương thức nhất định 
3. Các đặc trưng của giải thuật 
a. Tính xác định 
Ở mỗi bước của thuật toán các thao tác phải hết sức rõ ràng : Không thể gây nên sự nhập nhằng , tuỳ tiện . Nói một cách khác là trong cùng một điều kiện , hai bộ xử lý cùng thực hiện một bước của giải thuật thì phải cho cùng một kết quả 
b. Tính hữu hạn dừng 
 Giải thuật bao giờ cũng phải dừng sau một số hữu hạn bước 
3. Các đặc trưng của giải thuật 
c. Tính đúng đắn 
 Sau khi thực hiện tất cả các thao tác của thuật toán ta phải được kết quả mong muốn 
d. Tính phổ dụng 
 Thuật toán có thể giải bất kỳ bài toán nào trong cùng một lớp các bài toán 
3. Các đặc trưng của giải thuật ( tiếp ) 
e. Tính có đại lượng vào , đại lượng ra 
 Khi bắt đầu giải thuật bao giờ cũng nhận các đại lượng vào mà ta thường gọi là dữ liệu vào 
 Sau khi kết thúc , một thuật toán bao giờ cũng cho một số đại lượng ra tuỳ theo các chức năng mà thuật toán đảm nhiệm , chúng thường được gọi là dữ liệu ra . 
3. Các đặc trưng của giải thuật ( tiếp ) 
f. Tính có hiệu quả 
Tính có hiệu quả của giải thuật được đánh giá dựa trên các tiêu chuẩn sau 
 Dung lượng bộ nhớ cần có 
 Số các phép tính cần thực hiện 
 Thời gian cần thiết để chạy 
 Có dễ hiểu không 
 Có dễ cài đặt trên máy không 
4. Ngôn ngữ diÔn đạt giải thuật 
a. Liệt kê từng bước ( ngôn ngữ tự nhiên ) 
Liệt kê các bước thực hiện giải thuật theo thứ tự thực hiện 
Ví dụ 
b. Sơ đồ khối 
 Khối bắt đầu hoặc kết thúc 
 Khối thao tác 
 Nhập dữ liệu 
 Khối điều kiện 
 Chỉ hướng thực hiện của giải thuật 
Ví dụ 
4. Ngôn ngữ diÔn đạt giải thuật ( tiếp ) 
c. Dùng ngôn ngữ phỏng trình ( tựa ngôn ngữ lập trình ) 
Sử dụng cú pháp của một ngôn ngữ lập trình + Ngôn ngữ tự nhiên để diễn đạt giải thuật 
d. Dùng ngôn ngữ lập trình 
Dùng ngôn ngữ lập trình nào đó để viết giải thuật 
Hạn chế : 
Phụ thuộc vào ngữ nghĩa , cú pháp nặng nề , gò bó 
Không được nhiều người dùng ưa thích và sử dụng 
Ví dụ 
Ví dụ 
Lưu ý: Trong quá trình học môn học này , chủ yếu dùng ngôn ngữ phỏng trình tựa Pascal /C để diễn đạt giải thuật 
 Dữ liệu : Số, ký tự , hình ảnh , âm thanh  
Thuộc tính của một kiểu dữ liệu bao gồm : 
 Tên kiểu dữ liệu 
 Mièn giá trị 
 Kích thức lưu trữ 
 Tập các phép toán tác động lên KDL đó 
5. Kiểu dữ liệu 
 KDL cơ bản : 
 Rời rạc : Số nguyên , ký tự , logic, liệt kê , miền con 
 Liên tục : Số thực 
 KDL cấu trúc 
 Kiểu chuỗi (String) 
 Kiểu Mảng (Array) 
 Kiểu bản ghi ( Recorrd ) 
Kiểu tập hợp (Union) 
Các kiểu dữ liệu 
5. Kiểu dữ liệu 
 KDL trừu tượng 
 Danh sách móc nối (List) 
 Cây (Tree) 
 Đồ thị (Graph) 
 Tập hợp (union) 
Các kiểu dữ liệu 
5. Kiểu dữ liệu 
6. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật 
 North Wirth say that: 
Data Structures+Algorithms = Programs 
 Để xây dựng giải thuật phù hợp phải xác định nó tác động trên các kiểu dữ liệu nào 
Ví dụ : Làm nhuyễn các hạt đậu xay chứ không băm 
 Khi chọn lựa cấu trúc dữ liệu cần phải hiểu rõ những thao tác ( giải thuật ) sẽ tác động lên nó 
Ví dụ : Biểu diễn điểm của sinh viên dùng số chứ không dùng chữ 
- Cấu trúc dữ liệu thay đổi giải thuật thay đổi theo 
Ví dụ 
7. Tiêu chuẩn đánh giá CTDL 
a. Phản ánh đúng thực tế 
	 Quan trọng nhất , quyết định tính đúng đắn của toàn bộ bài toán 
c. Tiết kiệm tài nguyên hệ thống 
CPU, bộ nhớ 
VD: Khai báo tháng trong năm : Nên dùng kiểu byte thay vì kiểu int 
b. Phù hợp với các thao tác trên đó 
	 Giúp tăng tính hiệu quả của bài toán 
Tổng quan về các giải thuật và cấu trúc dữ liệu 
Chương I 
Khái niệm về cấu trúc dữ liệu và giải thuật 
Một số cú pháp điều khiển 
Đánh giá độ phức tạp của giải thuật 
II. Một số cú pháp điều khiển 
II. Một số cú pháp điều khiển 
 Có dạng : S1; S2; S3;  Sn 
 Với Si là các lệnh trọng chương trình 
 Để thực hiện câu lệnh tuần tự thì chương trình thực hiện lần lượt từ S1 đến Sn . Đầu ra của S1 là đầu vào của S2, đầu ra của S2 là đầu vào của S3 
1. Cú pháp tuần tự 
 Phải tôn trọng thứ tự thực hiện công việc , công việc nào làm trước thì phải viết lệnh trước 
Sơ đồ hoạt động 
 Có dạng V:=E 
với V chỉ tên biến , tên hàm ; E chỉ biểu thức 
2. Câu lệnh gán 
 Có dạng : Begin S1; S2; , Sn End; 
 Nó cho phep ghép nhiều câu lệnh lại để được coi như một câu lệnh 
3. Câu lệnh ghép 
II. Một số cú pháp điều khiển 
 Có dạng : If B Then S; 
 B là một biểu thức logic, S là một câu lệnh khác 
4. Câu lệnh điều kiện 
 Có dạng : If B Then S1 Else S2; 
 B là một biểu thức logic, S1, S2 là một câu lệnh khác 
Hoặc 
Sơ đồ hoạt động 
II. Một số cú pháp điều khiển 
 Có dạng : for i:=m to n do S; 
 Thực hiện câu lệnh S với i lấy giá trị nguyên từ m tới n (n>=m), với bước nhảy tăng bằng 1 
5. Câu lệnh lặp xác định 
Hoặc 
 Có dạng : for i:=n downto m do S; 
 Thực hiện tương tự như câu lệnh trên với bước nhảy giảm bằng 1 
II. Một số cú pháp điều khiển 
 Có dạng : while B do S; 
 Trong đó B là biểu thức logic; S là câu lệnh ; 
 Chừng nào B có giá trị True thì thực hiện S 
6. Câu lệnh lặp không xác định 
Hoặc 
 Có dạng : repeat S until B; 
 Trong đó B là biểu thức logic; S là câu lệnh ; 
 Lặp lại cho tới khi B có giá trị True 
Sơ đồ hoạt động 
II. Một số cú pháp điều khiển 
 Có dạng : go to n; 
 n là số hiệu của một bước trong chương trình 
 Thường hạn chế việc dùng Go to 
7. Câu lệnh nhảy 
 Có dạng : read( ); 
	 write();	 
8. Câu lệnh vào , ra 
II. Một số cú pháp điều khiển 
 Chương trình con Hàm 
function ( danh sách tham số ) 
Begin 
S1; S2; S3; ; Sn 
Return 
End; 
9. Chương trình con 
II. Một số cú pháp điều khiển 
9. Chương trình con 
 Chương trình con Thủ tục 
procedure ( danh sách tham số )> 
Begin 
S1; S2; S3; ; Sn 
End; 
II. Một số cú pháp điều khiển 
Tổng quan về các giải thuật và cấu trúc dữ liệu 
Chương I 
Khái niệm về cấu trúc dữ liệu và giải thuật 
Một số cú pháp điều khiển 
Đánh giá độ phức tạp của giải thuật 
III. Đánh giá độ phức tạp của giải thuật 
Thời gian 
Bộ nhớ 
Thực nghiệm 
Nhược điểm : 
Phải cài đặt bằng ngôn ngữ lập trình cụ thể 
Phụ thuộc trình độ người cài đặt 
Chọn mẫu thử 
Phụ thuộc nhiều vào phần cứng 
 Đánh giá theo hướng xấp xỉ tiệm cận qua các khái niệm toán học : O(), o(), 
 Quan tâm đến trường hợp trung bình 
Các tiêu chuẩn đánh giá độ phức tạp 
 Nếu thời gian thực hiện một giải thuật là T(n)=c.n 2 ( với c là hằng số ) thì ta nói : Độ phức tạp về thời gian của giải thuật này có cấp n 2 và ký hiệu T(n)=O(n 2 ) ( ký hiệu chữ O lớn ) 
2. Độ phức tạp về thời gian của giải thuật 
 Một cách tổng quát ta có thể định nghĩa : 
Một hàm f(n ) được xác định là O(g(n )) 
f(n )= O(g(n )) 
và được gọi là có cấp g(n ) nếu tồn tại các hàng số c và n 0 sao cho : 
f(n ) c .g(n ) khi n n 0 
Ví dụ 
Quy tắc tổng : 
Giả sử T 1 (n) và T 2 (n) là thời gian thực hiện của 2 đoạn chương trình P 1 và P 2 mà T 1 (n)=O(f(n)) và T 2 (n)=O(g(n)) thì thời gian thực hiện P 1 và P 2 kế tiếp nhau sẽ là : 
T(n )=T 1 (n)+T 2 (n)=O(max(f(n), g(n))) 
3. Xác định độ phức tạp về thời gian 
Quy tắc nhân 
Nếu tương ứng với P 1 và P 2 là T 1 (n)= O(f(n )), T 2 (n)= O(g(n )) thì thời gian thực hiện P 1, P 2 lồng nhau sẽ là : 
T(n )=T 1 (n).T 2 (n)= O(f(n).g(n )) 
Ví dụ 
Ví dụ 
4. Độ phức tạp về thời gian của các cú pháp điều khiển 
Câu lệnh gán , đọc , viết , nhẩy : 
 Có thời gian thực hiện =c ( hằng số ) đánh giá là O(1) 
b. Câu lệnh ghép 
Begin S1; S2; , Sn End; 
Thời gian thực hiện theo luật cộng 
 Khái niệm : Phép toán tích cực : Là phép 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 . Ví dụ : 
4. Độ phức tạp về thời gian của các cú pháp điều khiển 
c. Câu lệnh điều kiện 
If B then S1 Else S2; 
Thời gian thực hiện là O(Max(f 1 (n), f 2 (n))) 
Trong đó : Thời gian thực hiện S 1 là T 1 (n)=O(f 1 (n)); 
	 S 2 là T 2 (n)=O(f 2 (n)) 
4. Độ phức tạp về thời gian của các cú pháp điều khiển 
d. Câu lệnh lặp While 
 While B Do S; 
 Nếu thời gian thực hiện S là T(n )= O(f(n )) và có g(n ) lần thực hiện S trong vòng lặp While ( tối đa ) thì thời gian thực hiện vòng lặp là O(f(n).g(n )) 
e. Câu lệnh lặp Repeat 
 Repeat S1; S2; , Sn Until B; 
 Nếu thời gian thực hiện S1, S2, , Sn là T(n )= O(f(n )) và số lần lặp tối đa là g(n ) thì thời gian thực hiện vòng lặp là O(f(n).g(n )) 
4. Độ phức tạp về thời gian của các cú pháp điều khiển 
f. Câu lệnh lặp xác định 
 for i:=m to n do S; 
 Nếu thời gian thực hiện S là T(n )= O(f(n )) và có g(n ) lần lặp For thì thời gian thực hiện là O(f(n).g(n )) 
Ví dụ về đánh giá độ phức tạp 
5. Phân lớp các thuật toán  
 Phức tạp đa thức : O(1), O(n), O(n.logn ), O(n 2 ), O(n 3 ) 
 Phức tạp hàm mũ : O(2 n ) 
 Phức tạp giai thừa : O(n!) 
Mục tiêu thiết kế giải thuật : Đưa bài toán về độ phức tạp đa thức 
Đồ thị của một số hàm số 
So sánh các độ phức tạp 
Bảng giá trị của một số hàm số 
4 
8 
4 
2 
2 
1 
2.147.483.648 
32768 
1024 
160 
32 
5 
6536 
4096 
256 
64 
16 
4 
256 
512 
64 
24 
8 
3 
16 
64 
16 
8 
4 
2 
2 
1 
1 
0 
1 
0 
2n 
n3 
n2 
nlog2n 
n 
long2n 
So sánh các độ phức tạp 
The End ! 
Ví dụ : Chương trình quản lý điểm của sinh viên 
Chương trình quản lý điểm của sinh viên , cần lưu điểm số của 3 sinh viên . 
Do mỗi sinh viên có 4 điểm số ứng với 4 môn học dữ liệu có dạng bảng sau : 
SV 
Môn 1 
Môn 2 
Môn 3 
Môn 4 
SV 1 
5 
6 
7 
0 
SV 2 
6 
5 
8 
8 
SV 3 
5 
5 
9 
7 
Ví dụ : Chương trình quản lý điểm của sinh viên 
Phương án 2 : Sử dụng mảng hai chiều 3 X 4, phần tử A[i,j] là điểm thi môn j của sinh viên i 
7 
9 
5 
5 
8 
8 
5 
6 
0 
7 
6 
5 
A= 
Phương án 1 : Sử dụng mảng một chiểu 12 phần tử , nhóm 4 phần tử là điểm của 1 SV 
7 
9 
5 
5 
8 
8 
5 
6 
0 
7 
6 
5 
SV1	 SV2	 SV3 
Truy xuất điểm j của sinh viên i 
Bảng ( dòng i, cột j)= A[(i-1)* số cột+j ] 
Dùng sơ đồ khối 
Begin 
m,n 
m=n 
m>n 
UCLN = m 
End 
Đúng 
Sai 
m:=m-n 
Đúng 
n:=n-m 
Sai 
Tìm UCLN của 2 số nguyên dương m và n 
Dùng ngôn ngữ phỏng trình 
Function UCLN (m,n ) { Tìm ước số chung lớn nhất của hai số nguyên dương m và n} 
Begin 
Nhập m, n nguyên dương 
While mn do 
If m>n then m:=m-n else n:=n-m 
UCLN:=m 
End; 
Dùng ngôn ngữ lập trình 
# includ e 
# include 
void main() 
{ 
int m, n; 
printf("Nhap 2 so nguyen duong m,n\n"); 
scanf("%d%d",&m,&n ); 
while (m!=n) 
{ 
if (m>n) 
m=m-n; 
else n=n-m; 
} 
printf("UCLN =%d",m); 
getch (); 
} 
Bài toán : Tìm UCLN của 2 số nguyên dương m và n 
Dùng liệt kê từng bước 
Bước 1 : Nhập hai số nguyên dương 
Bước 2 : Nếu m=n sang bước 4 ; ngược lại sang bước 3 
Bước 3 : Nếu m>n thì đặt m=m-n về bước 2 
	 Nếu m<n thì đặt n=n-m về bước 2 
Bước 4 : Trả lời UCLN=m, Kết thúc 
Bài toán : Tìm UCLN của 2 số nguyên dương m và n 
Ví dụ : Diễn đạt bài toán thành 2 thành phần 
Diễn đạt bài toán giải phương trình bậc 2 
Input : Các hệ số a,b,c 
Outpu t: Thông báo nghiệm x1, x2; nghiệm kép x; hoặc vô nghiệm 
Diễn đạt bài toán Tìm ước số chung lớn nhất 
Input : Hai số nguyên dương m, n 
Outpu t: ước số chung lớn nhất của m, n 
Sơ đồ hoạt động của lệnh điều kiện 
B 
S 
True 
False 
B 
S 1 
True 
False 
S 2 
Sơ đồ hoạt động của lệnh lặp không biết trước 
B 
S 
True 
False 
True 
B 
S 
False 
Hoặc 
f. Câu lệnh lặp xác định 
For i:=1 to n do x:=x+1 
Thời gian thực hiện là O(n.1)=O(n) 
For i:=1 to n do 
 For j:=1 to n do x:=x+1 
Thời gian thực hiện là O(n.n)=O(n 2 ) 
Ví dụ : Xác định độ phức tạp 
Tính : e x =1+x/1!+x 2 /2!++ x n /n ! 
Program EXP1 ; 
{ Tính từng số hạng rồi cộng lại } 
Begin 
Read(x); 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; 
 Phép toán tích cực p:=p*x/j; 
 Nó thực hiện 	1+2++n=n(n+1)/2 lần 
 Độ phức tạp T(n)=O(n 2 ) 
Ví dụ : Xác định độ phức tạp 
Tính : e x =1+x/1!+x 2 /2!++ x n /n ! ( cách 2) 
Tách x 2 /2!=x/1!.x/2, , x n /n !=x n-1 /(n-1)!.x/2 
Progam EXP2; 
Begin 
Read(x); s:=1;p:=1; 
For i:=1 to n do 
Begin 
p:=p*x/i; 
S:=s+p; 
End; 
Phép toán tích cực p:=p* x/i ; 
Nó thực hiện n lần 
 Độ phức tạp T(n)=O(n) 
Ví dụ : Xác định phép toán tích cực 
Tính : e x =1+x/1!+x 2 /2!++ x n /n ! 
Tách x 2 /2!=x/1!.x/2, , x n /n !=x n-1 /(n-1)!.x/2 
Progam EXP2; 
Begin 
Read(x); s:=1;p:=1; 
For i:=1 to n do 
Begin 
p:=p*x/i; 
S:=s+p; 
End; 
Phép toán tích cực p:=p* x/i ; 
Đánh giá độ phức tạp bằng ký pháp O() 
a. f(n )=n 3 +4n+4 
g(n )=n 3 : vì chọn hằng số c=9 và n 0 =1 thì 
	 n 3 +4n+4=1 
 Độ phức tạp f(n )=O(n 3 ) 
b. f(n )=500n 2 +4nlogn+4n+3 
g(n )=n 2 : chọn hằng số c=511 và n 0 =1 thì 
4nlogn=1 
4n=1 
3=1 
 500n 2 +4nlogn+4n+3<= 500n 2 + 4n 2 + 4n 2 + 3n 2 =511n 2 
Độ phức tạp f(n )=O(n 2 ) 
Đánh giá độ phức tạp bằng ký pháp O() 
c. f(n )=n 4 +4n 3 +4n 2 +10000 
g(n )=n 4 vì chọn hằng số c=10009 và n 0 =1 
n 4 +4n 3 +4n 2 +10000=1 
 n 4 +4n 3 +4n 2 +10000=1 
 Độ phức tạp f(n )=O(n 4 ) 
d. f(n )=n!+100n 3 +n 2 
g(n )=n! vì chọn hằng số c=102 và n 0 =10 ta có 
n!+100n 3 +n 2 =10 
 n!+100n 3 +n 2 =10 
 Độ phức tạp f(n )= O(n !) 
For i:=1 to n do 
	 	 c[i,i ]:=c[i,i]+100 
P1 
Thời gian thực hiện P1 là : T 1 (n)= O(n ) 
S:=0; 
For i:=1 to n do 
For j:=1 to n do 
If c[i,j ]>0 then S:= S+c[i,j ] 
P2 
Thời gian thực hiện P2 là : T 2 (n)=O(n 2 ) 
 T hời gian thực hiện P 1 và P 2 kế tiếp nhau sẽ là : T(n )=T 1 (n)+T 2 (n)= O(max( n , n 2 ))= O( n 2 ) 
Ví dụ : Quy tắc cộng 
For i:=1 to N.N do 
Ví dụ : Quy tắc nhân 
For j:=1 to N do 
S:= S+c[j ] 
Đoạn chương trình P1. 
Thời gian thực hiện P1 là : T 1 (n)= O(n ). Vì thực hiện n lần tính tổng 
Đoạn chương trình P2. 
Thời gian thực hiện P2 là : T 2 (n)=O(n 2 ). Vì thực hiện n 2 lần đoạn chương trình P1 
 Thời gian thực hiện P 1, P 2 lồng nhau sẽ là : 
T(n )=T 1 (n)T 2 (n)= O(n . n 2 )=O( n 3 ) 
Cú pháp tuần tự 
S1 
S2 
S3 
Sn