Giáo trình Cấu trúc dữ liệu và giải thuật 1 - Nghề: Công nghệ thông tin (Ứng dụng phần mềm)

CỤC HẢNG HẢI VIỆT NAM

TRƯỜNG CAO ĐẲNG HÀNG HẢI I

GIÁO TRÌNH

MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ

GIẢI THUẬT 1

NGHỀ: CÔNG NGHỆ THÔNG TIN

(ỨNG DỤNG PHẦN MỀM)

TRÌNH ĐỘ: CAO ĐẲNG, TRUNG CẤP

(Ban hành kèm theo Quyết định số

/QĐ-CĐHH I, ngày tháng năm 2017

của Hiệu trưởng Trường Cao đẳng Hàng hải I )

Hải Phòng, năm 2017

TUYÊN BỐ BẢN QUYỀN

Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được

phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo.

Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh

thiếu lành mạnh sẽ bị nghiêm cấm.

- 1 -

LỜI GIỚI THIỆU

Công nghệ thông tin ngày càng được ứng dụng rộng rãi và hiệu quả trong mọi

lĩnh vực khoa học tự nhiên và xã hội. Để thực hiện một đề án tin học là chuyển bài

toán thực tế thành bài toán có thể giải quyết được trên máy tính thì vấn đề thiết kế,

lựa chọn cấu trúc dữ liệu và giải thuật là một giai đoạn quan trọng trong quy trình

thiết kế và xây dựng phần mềm.

Nhằm giới thiệu những kiến thức cơ bản về cấu trúc dữ liệu và giải thuật, Tổ

Tin học - Trường Cao đẳng Hàng hải I đã phối hợp với các nhà xuất bản trên địa bàn

thành phố xuất bản giáo trình “Cấu trúc dữ liệu và giải thuật 1”. Giáo trình do ThS.

Nguyễn Quang Huy biên soạn dựa theo đề cương chi tiết qui định của Trường Cao

đẳng Hàng hải I và được Hội đồng khoa học của trường thẩm định. Đây là môn học

cơ sở cùng tên trong chương trình đào tạo nghề Công nghệ thông tin (Ứng dụng

phần mềm). Giáo trình gồm 3 chương với nội dung như sau:

Chương 1: Giới thiệu tổng quan về cấu trúc dữ liệu và giải thuật, bao gồm các

khái niệm về cấu trúc dữ liệu và giải thuật, mối quan hệ giữa chúng, vấn đề thiết kế

cấu trúc dữ liệu, thiết kế và phân tích giải thuật, đánh giá độ phức tạp của giải thuật,

đệ quy và giải thuật đệ quy, một phương pháp thiết kế giải thuật khá quan trọng, nhất

là với các giải thuật biểu diễn các thao tác xử lý cấu trúc dữ liệu dạng cây.

Chương 2: Các kiểu dữ liệu cơ sở, khái niệm, phạm vi lưu trữ dữ liệu, các

phép xử lý của các kiểu dữ liệu cơ sở như: kiểu số, chuỗi, logic, tập hợp, mảng một

chiều, mảng nhiều chiều, cấu trúc, con trỏ, tệp tin. Sử dụng các kiểu dữ liệu cơ sở

trong việc mô tả các đối tượng trong các ngôn ngữ lập trình bậc cao như Pascal, C,

C⁺⁺, Java.

Chương 3: Danh sách tuyến tính, một loại cấu trúc dữ liệu phổ biến trong các

bài toán tin học. Trong chương này trình bày các phương pháp lưu trữ danh sách và

các thao tác xử lý tương ứng với mỗi loại danh sách.

Bài tập sau mỗi chương đã được chọn lọc ở mức độ phù hợp với sinh viên,

qua đó giúp cho sinh viên hiểu sâu sắc thêm về bài giảng, củng cố thêm về kỹ thuật

cài đặt chương trình và nắm bắt được một số kiến thức không được trực tiếp giới

thiệu trong bài giảng.

Để học tốt môn học này đòi hỏi sinh viên phải thành thạo ít nhất một ngôn

ngữ lập trình cơ bản như Pascal, C hay C⁺⁺, ..., thành thạo các kỹ thuật lập trình như:

cấu trúc rẽ nhánh, cấu trúc lặp, kỹ thuật lập trình đơn thể (sử dụng hàm, thủ tục).

Mặc dù tác giả có nhiều cố gắng trong công tác biên soạn song sẽ khó tránh

- 2 -

khỏi thiếu sót, tôi rất mong nhận được ý kiến đóng góp của các bạn đồng nghiệp và

bạn đọc để lần xuất bản sau được hoàn thiện hơn.

Mọi ý kiến đóng góp xin gửi về Tổ Tin học - Trường Cao đẳng Hàng hải I:

498 Đà Nẵng - Đông Hải I - Hải An - Hải Phòng.

Xin trân trọng giới thiệu./.

Hải Phòng, ngày 18 tháng 10 năm 2017

Tham gia biên soạn:

`

Chủ biên: ThS. Nguyễn Quang huy

- 3 -

MỤC LỤC

TUYÊN B Ố B Ả N QUY Ề N ..................................................................................- 1 -

L Ờ I GI Ớ I THI Ệ U..................................................................................................- 2 -

M Ụ C L Ụ C.............................................................................................................- 4 -

GIÁO TRÌNH MÔN H Ọ C....................................................................................- 6 -

CHƯƠNG 1:..........................................................................................................- 7 -

THI Ế T K Ế VÀ PHÂN TÍCH GI Ả I THU Ậ T........................................................- 7 -

1. M ở đầ u ...........................................................................................................- 7 -

1.1. Xây dựng cấu trúc dữ liệu ........................................................................- 7 -

1.2. Xây dựng giải thuật ..................................................................................- 7 -

1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật .....................................- 8 -

2. Thi ế t k ế gi ả i thu ậ t ..........................................................................................- 8 -

2.1. Giải thuật .................................................................................................- 8 -

3. Phân tích gi ả i thu ậ t.........................................................................................- 9 -

3.1. Tính hiệu quả của giải thuậ t ................................................................. - 10 -

3.2. Đánh giá thời gian thực hiện của giải thuật ......................................... - 10 -

3.3. Đánh giá độ phức tạp tính toán của giải thuật ..................................... - 11 -

3.4. Xác định độ phức tạp tính toán ............................................................. - 13 -

4. M ộ t s ố gi ả i thu ật cơ bả n.............................................................................. - 14 -

4.1. Hoán vị hai phần tử .............................................................................. - 14 -

4.2. Tìm số lớn nhất, nhỏ nhất ..................................................................... - 15 -

4.3. Đệ quy ................................................................................................... - 16 -

4.4. Chia để trị ............................................................................................. - 19 -

Câu hỏi và bài tập ........................................................................................ - 23 -

CHƯƠNG 2:....................................................................................................... - 24 -

CÁC KI Ể U D Ữ LI Ệ U ........................................................................................ - 24 -

1. Các ki ể u d ữ li ệu cơ bả n............................................................................... - 24 -

1.1. Kiểu số ................................................................................................... - 24 -

1.2. Kiểu kí tự, chuỗ i .................................................................................... - 26 -

1.3. Kiểu logi c .............................................................................................. - 27 -

- 4 -

2. Ki ể u d ữ li ệ u có c ấ u trú c ............................................................................. - 27 -

2.1. Mảng một chiều ..................................................................................... - 27 -

2.2. Mảng nhiều chiều .................................................................................. - 27 -

2.3. Cấu trúc ................................................................................................. - 28 -

2.4. Kiểu con trỏ .......................................................................................... - 28 -

2.5. Kiểu file (Tệp tin ).................................................................................. - 29 -

3. Ki ể u t ậ p h ợ p ................................................................................................ - 29 -

3.1. Khái niệ m .............................................................................................. - 29 -

3.2.Các phép xử lý kiểu dữ liệu tập hợp ...................................................... - 29 -

3.3.Cài đặt tập hợp ...................................................................................... - 30 -

Câu hỏi và bài tập ........................................................................................ - 30 -

CHƯƠNG 3:....................................................................................................... - 32 -

M Ả NG, DANH SÁCH VÀ CÁC KI Ể U D Ữ LI Ệ U TR ỪU TƯỢ N G ............... - 32 -

1. M ả ng ........................................................................................................... - 33 -

1.1. Khái ni ệ m .............................................................................................. - 33 -

1.2. C ấu trúc lưu trữ c ủ a m ả ng .................................................................... - 34 -

2. Danh sách liên k ế t ....................................................................................... - 35 -

2.1. Danh sách liên k ết đơn ......................................................................... - 35 -

2.2. Danh sách liên k ế t vòng ........................................................................ - 46 -

2.3. Danh sách liên k ế t ké p .......................................................................... - 48 -

3. Các ki ể u d ữ li ệ u tr ừu tượ ng ........................................................................ - 64 -

3.1. Ngăn xế p ............................................................................................... - 64 -

3.2. Hàng đợ i ............................................................................................... - 69 -

Câu hỏi và bài tập ........................................................................................ - 76 -

TÀI LIỆU THAM KHẢO .................................................................................. - 77 -

- 5 -

GIÁO TRÌNH MÔN HỌC

Tên môn học: Cấu trúc dữ liệu và giải thuật 1

Mã môn học: MH.6480202.10

Vị trí, tính chất, ý nghĩa và vai trò của môn học

- Vị trí: Môn học được học sau các môn học Tin học, Lập trình căn bản.

- Tính chất: Cấu trúc dữ liệu và giải thuật 1 là môn cơ sở bắt buộc, mang tính

lý thuyết, gắn liền với bài toán ứng dụng cụ thể như quản lý, sắp xếp, tìm kiếm.

- Ý nghĩa và vai trò của môn học: Cấu trúc dữ liệu và giải thuật là một trong

những môn học cơ bản của sinh viên ngành Công nghệ thông tin. Các cấu trúc dữ

liệu và các giải thuật được xem như là hai yếu tố quan trọng nhất trong lập trình,

đúng như câu nói nổi tiếng của Niklaus Wirth: Chương trình = Cấu trúc dữ liệu +

Giải thuật (Programs = Data Structures + Algorithms). Nắm vững các cấu trúc dữ

liệu và các giải thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng

phần mềm cũng như sử dụng các công cụ lập trình hiện đại.

Mục tiêu của môn học:

- Kiến thức: Trình bày được mối quan hệ giữa cấu trúc dữ liệu và giải thuật

trong việc xây dựng chương trình; ý nghĩa, cấu trúc, cách khai báo, các thao tác của

các loại cấu trúc dữ liệu: mảng, danh sách liên kết và các giải thuật cơ bản xử lý các

cấu trúc dữ liệu đó;

- Kỹ năng: Xây dựng được cấu trúc dữ liệu và mô tả tường minh các giải thuật

cho một số bài toán ứng dụng cụ thể; Cài đặt được một số giải thuật trên ngôn ngữ

lập trình C;

- Năng lực tự chủ và trách nhiệm: Coi việc học môn này là một nền tảng cho

các môn học chuyên môn tiếp theo, nghiêm túc và tích cực trong việc học lý thuyết

và làm bài tập, chủ động tìm kiếm các nguồn tài liệu liên quan đến môn học.

Nội dung môn học:

- 6 -

CHƯƠNG 1:

THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT

Mã chương: MH.6480202.10.01

Giới thiệu:

Giới thiệu tổng quan về cấu trúc dữ liệu và giải thuật, bao gồm các khái niệm

về cấu trúc dữ liệu và giải thuật, mối quan hệ giữa chúng, vấn đề thiết kế cấu trúc

dữ liệu, thiết kế và phân tích giải thuật, đánh giá độ phức tạp của giải thuật, đệ quy

và giải thuật đệ quy, một phương pháp thiết kế giải thuật khá quan trọng, nhất là với

các giải thuật biểu diễn các thao tác xử lý cấu trúc dữ liệu dạng cây.

Mục tiêu:

- Trình bày được mối quan hệ giữa cấu trúc dữ liệu và giải thuật;

- Mô tả được các cách tư duy về tiến trình phân tích và thiết kế thuật toán;

- Biết cách đánh giá độ phức tạp thuật toán;

- Hiểu được một số giải thuật cơ bản;

- Viết tường minh một số giải thuật;

- Nghiêm túc, tỉ mỉ trong việc học và vận dụng vào làm bài tập.

Nội dung chính:

1. Mở đầu

1.1. Xây dựng cấu trúc dữ liệu

Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu

để xử lý. Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ

liệu đưa ra (output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương

trình có ý nghĩa rất quan trọng trong toàn bộ hệ thống chương trình. Việc xây dựng

cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng như công sức của người lập

trình trong việc thiết kế, cài đặt chương trình.

1.2. Xây dựng giải thuật

Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán

dùng để chỉ phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật

có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow

chart) hoặc bằng mã giả (pseudo code). Trong thực tế, giải thuật thường được minh

họa hay thể hiện bằng mã giả tựa trên một hay một số ngôn ngữ lập trình nào đó

(thường là ngôn ngữ mà người lập trình chọn để cài đặt thuật toán), chẳng hạn như

C, Pascal, …

Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu

- 7 -

tiến hành xây dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở

của cấu trúc dữ liệu đã được chọn. Để giải quyết một vấn đề có thể có nhiều phương

pháp, do vậy sự lựa chọn phương pháp phù hợp là một việc mà người lập trình phải

cân nhắc và tính toán. Sự lựa chọn này cũng có thể góp phần đáng kể trong việc

giảm bớt công việc của người lập trình trong phần cài đặt thuật toán trên một ngôn

ngữ cụ thể.

1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật

Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng

thức:

Cấu trúc dữ liệu + Giải thuật = Chương trình

Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc

thể hiện chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian. Khi có cấu

trúc dữ liệu mà chưa tìm ra thuật giải thì không thể có chương trình và ngược lại

không thể có Thuật giải khi chưa có cấu trúc dữ liệu. Một chương trình máy tính chỉ

có thể được hoàn thiện khi có đầy đủ cả Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải

thuật xử lý dữ liệu theo yêu cầu của bài toán đặt ra.

2. Thiết kế giải thuật

2.1. Giải thuật

Giải thuật (algorithm) là một trong những khái niệm quan trọng nhất trong tin

học. Thuật ngữ giải thuật xuất phát từ nhà toán học Ả-rập Abu Ja’far Mohammed

ibn Musa al Khowarizmi (khoảng năm 825). Tuy nhiên, trong lúc bấy giờ và trong

nhiều thế kỷ sau, nó không mang nội dung như ngày nay chúng ta quan niệm. Giả

thuật nổi tiếng nhất, có từ thời cổ Hy Lạp là giải thuật Euclid, giải thuật tìm ước

chung lớn nhất của hai số nguyên. Có thể mô tả giải thuật này như sau:

* Giải thuật Euclid

Vào: m, n nguyên dương

Ra: d, ước số chung lớn nhất của m và n.

Phương pháp

Bước 1: Tìm r, phần dư của phép chia m cho n

Bước 2: Nếu r = 0, thì d  n (gán giá trị của n cho d) và dừng lại

Ngược lại, thì m  n, n  r và quay lại bước 1

2.1.1. Khái niệm

Giả thuật là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép

toán hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra.

- 8 -

2.1.2. Đặc trưng của giải thuật

Định nghĩa trên, còn chứa đựng nhiều điều chưa rõ ràng. Để hiểu đầy đủ ý

nghĩa của giải thuật, chúng ta nêu ra 5 đặc trưng của nó:

* Bộ dữ liệu vào: Mỗi giải thuật cần có một số lượng (có thể bằng 0) dữ liệu

vào (input). Đó là các giá trị cần đưa vào khi giải thuật bắt đầu làm việc. Các dữ liệu

này cần được lấy từ tập hợp các giá trị cụ thể nào đó. Chẳng hạn, trong giải thuật

Euclid nói trên, m và n là các dữ liệu vào lấy từ tập các số nguyên dương.

* Dữ liệu ra: Mỗi giải thuật cần có một hoặc nhiều dữ liệu ra. Đó là các giá

trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự thực hiện

giải thuật. Trong giải thuật Euclid có một dữ liệu ra, đó là d, khi thực hiện đến bước

2 và phải dừng lại (trường hợp r = 0), giá trị của d là ước số chung lớn nhất của m

và n.

* Tính xác định: Mỗi bước của giải thuật cần phải được mô tả một cách chính

xác, chỉ có một cách biểu diễn duy nhất. Hiển nhiên đây là một đòi hỏi rất quan

trọng. Bởi vì, nếu một bước có thể hiểu theo nhiều cách khác nhau, thì cùng một dữ

liệu vào, những người thực hiện giải thuật khác nhau có thể dẫn đến kết quả khác

nhau. Để đảm được bảo tính xác định giải thuật cần phải được mô tả trong các ngôn

ngữ lập trình. Trong các ngôn ngữ này, các mệnh đề được tạo thành theo quy tắc, cú

pháp nghiêm ngặt và chỉ có một ý nghĩa duy nhất.

* Tính khả thi: Tất cả các phép toán có mặt trong các bước của giải thuật phải

đủ đơn giản. Điều này có nghĩa là, người lập trình có thể thực hiện chỉ bằng giấy

trắng và bút trong khoảng thời gian hữu hạn. Chẳng hạn, với giải thuật Euclid, ta chỉ

thực hiện các phép chia số nguyên, các phép gán và phép so sánh để biết được r = 0

hay r ≠ 0.

* Tính dừng: Với mọi bộ dữ liệu vào thỏa mãn các điều kiện của dữ liệu vào,

giải thuật phải dừng lại sau một số hữu hạn các bước thực hiện. Chẳng hạn giải thuật

Euclid thỏa mãn điều kiện này. Bởi vì, khi ta thực hiện bước 1 thì giá trị r nhỏ hơn

n, nếu r ≠ 0 thì giá trị của n ở bước 2 là giá trị của r ở bước trước, ta có n>r = n₁>r₁

= n₂>r₂, … Dãy số nguyên dương giảm dần cần phải kết thúc ở 0, do đó sau một số

hữu hạn bước giá trị của r phải bằng 0, giải thuật dừng.

3. Phân tích giải thuật

Giả sử đối với một bài toán nào đó chúng ta có một số giải thuật để giải. Một

câu hỏi đặt ra là, chúng ta cần chọn giải thuật nào trong số các giải thuật đã có để

giải bài toán một cách hiệu quả nhất. Sau đây ta phân tích giả thuật và đánh giá độ

phức tạp tính toán của nó.

- 9 -

3.1. Tính hiệu quả của giải thuật

Khi giải quyết một vấn đề, chúng ta chọn trong số các giải thuật, một giải

thuật mà chúng ta cho là tốt nhất. Vì vậy ta cần lựa chọn giải thuật dựa trên cơ sở

nào? Thông thường ta dựa trên hai tiêu chuẩn sau đây:

1. Giải thuật đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)

2. Giải thuật sử dụng tiết kiệm nhất nguồn tài nguyên của máy tính và đặc

biệt, chạy nhanh nhất có thể được

Khi ta viết một chương trình chỉ để sử dụng một số ít lần và cái giá của thời

gian viết chương trình vượt xa cái giá của chạy chương trình thì tiêu chuẩn (1) là

quan trọng nhất. Nhưng có trường hợp là ta cần viết các chương trình (thủ tục hoặc

hàm) để sử dụng nhiều lần, cho nhiều người sử dụng, khi đó giá của thời gian chạy

chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các thủ tục sắp xếp, tìm kiếm được

sử dụng rất nhiều lần, cho rất nhiều người trong các bài toán khác nhau. Trong trường

hợp này ta cần dựa trên tiêu chuẩn (2). Ta sẽ cài đặt giải thuật có thể rất phức tạp,

miễn là chương trình nhận được chạy nhanh hơn các giải thuật khác.

Tiêu chuẩn (2) được xem là tính hiệu quả của giải thuật. Tính hiệu quả của

giải thuật gồm hai nhân tố cơ bản.

- Dung lượng nhớ cần thiết để lưu giữ các dữ liệu vào, các kết quả tính toán

trung gian và các kết quả của giải thuật.

- Thời gian cần thiết để thực hiện giải thuật (ta gọi là thời gian chạy chương

trình, thời gian này không phụ thuộc vào các yếu tố vật lý của máy tính như tốc độ

xử lý của máy tính, ngôn ngữ viết chương trình, …)

Chúng ta sẽ chỉ quan tâm đến thời gian thực hiện giải thuật. Vì vậy khi nói

đến đánh giá độ phức tạp của giải thuật, có nghĩa là ta nói đến đánh giá thời gian

thực hiện. Một giải thuật có hiệu quả được xem là giải thuật có thời gian chạy ít hơn

các giải thuật khác.

3.2. Đánh giá thời gian thực hiện của giải thuật

Có hai cách tiếp cận để đánh giá thời gian thực hiện của một giải thuật.

a. Phương pháp thử nghiệm

Chương trình được viết và cho chạy với các dữ liệu vào khác nhau trên một

máy tính nào đó. Thời gian chạy chương trình phụ thuộc vào các yếu tố sau đây:

1. Các dữ liệu vào;

2. Chương trình dịch, để chuyển chương trình nguồn thành chương trình mã

máy;

- 10 -

3. Tốc độ thực hiện các phép toán của máy được sử dụng để chạy chương

trình.

Vì thời gian chạy chương trình phụ thuộc vào nhiều yếu tố, nên ta không thể

biểu diễn chính xác thời gian chạy là bao nhiêu đơn vị thời gian chuẩn, chẳng hạn

nó là bao nhiêu giây nếu không nêu các cấu hình hệ máy thực hiện.

b. Phương pháp lý thuyết

Ta sẽ coi thời gian thực hiện của giải thuật như là một hàm số của kích thước

dữ liệu vào. Kích thước của dữ liệu vào là một tham số đặc trưng cho dữ liệu vào,

nó có ảnh hưởng quyết định đến thời gian thực hiện của chương trình. Đơn vị tính

kích thước của dữ liệu vào phụ thuộc vào các giải thuật cụ thể. Chẳng hạn, đối với

các giải thuật sắp xếp mảng, thì kích thước của dữ liệu vào là số thành phần (phần

tử) của mảng, đối với giải thuật giải hệ n phương trình tuyến tính với n ẩn, ta chọn

n là kích thước. Thông thường dữ liệu vào là một số nguyên dương n. Ta sẽ sử dụng

hàm số T(n), trong đó n là kích thước dữ liệu vào, để biểu diễn thời gian thực hiện

của một giải thuật.

Có thể xác định thời gian thực hiện T(n) là số phép toán sơ cấp cần phải tiến

hành khi thực hiện giải thuật. Các phép toán sơ cấp là các phép toán mà thời gian

thực hiện bị chặn trên bởi một hằng số chỉ phụ thuộc vào cách cài đặt được sử dụng.

Chẳng hạn các phép toán số học +, -, *, /, các phép toán so sánh =, !=, … là các phép

toán sơ cấp.

3.3. Đánh giá độ phức tạp tính toán của giải thuật

Một phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật

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 giải thuật 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 giải thuật. 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.

3.3.1. Thời gian thực hiện chương trình.

Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào,

ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.

Ví dụ: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn

- 11 -

trong đó c là một hằng số.

Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) ≥ 0 ∀ n

≥ 0.

3.3.2. Ðơn vị đo thời gian thực hiện.

Ðơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút

giây, ... mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính

lý tưởng.

Ví dụ: Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có

nghĩa là chương trình ấy cần Cn chỉ thị thực thi.

3.3.3. Thời gian thực hiện trong trường hợp xấu nhất.

Nói chung thì thời gian thực hiện chương trình 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 chương trình 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.

3.3.4. Khái niệm độ phức tạp của giải thuật

Giả sử ta có hai giải thuật P₁và P₂với thời gian thực hiện tương ứng là T₁(n)

= 100n²(với tỷ suất tăng là n²) và T₂(n) = 5n³(với tỷ suất tăng là n³). Giải thuật nào

sẽ thực hiện nhanh hơn? Câu trả lời phụ thuộc vào kích thước dữ liệu vào. Với n <

20 thì P₂sẽ nhanh hơn P₁(T₂< T₁), do hệ số của 5n³nhỏ hơn hệ số của 100n²(5 <

100). Nhưng khi n > 20 thì ngươc lại do số mũ của 100n²nhỏ hơn số mũ của 5n³(2

< 3). Ở đây chúng ta chỉ nên quan tâm đến trường hợp n > 20 vì khi n < 20 thì thời

gian thực hiện của cả P₁và P₂đều không lớn và sự khác biệt giữa T₁và T₂là không

đáng kể.

Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện

chương trình thay vì xét chính bản thân thời gian thực hiện.

Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N₀

sao cho T(n) ≤ Cf(n) với mọi n ≥ N₀(tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu

T(n) là O(f(n)) (đọc là “ô của f(n)”)

Ví dụ: T(n) = (n+1)²có tỷ suất tăng là n²nên T(n) = (n+1)²là O(n²)

- 12 -

Chú ý: O(C.f(n)) = O(f(n)) với C là hằng số. Ðặc biệt O(C) = O(1)

Nói cách khác độ phức tạp tính toán của giải thuật là một hàm chặn trên của

hàm thời gian. Vì hằng nhân tử C trong hàm chặn trên không có ý nghĩa nên ta có

thể bỏ qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau: log₂n, n,

nlog₂n, n², n³, 2ⁿ, n!, nⁿ. Ba hàm cuối cùng ta gọi là dạng hàm mũ, các hàm khác gọi

là hàm đa thức. Một giải thuật 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 giải thuật có độ

phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật.

Vì ký hiệu log₂n thường có mặt trong độ phức tạp nên trong khôn khổ tài liệu

này, ta sẽ dùng logn thay thế cho log₂n với mục đích duy nhất là để cho gọn trong

cách viết.

Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến hiệu quả của thời

gian thực hiện của chương trình nên ta có thể xem việc xác định thời gian thực hiên

của chương trình chính là xác định độ phức tạp của giải thuật.

3.4. Xác định độ phức tạp tính toán

Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản.

Tuy nhiên ta có thể tuân theo một số nguyên tắc sau:

3.4.1. Qui tắc cộng

Nếu T₁(n) và T₂(n) là thời gian thực hiện của hai đoạn chương trình P₁và P₂;

và T₁(n)=O(f(n)), T₂(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình

đó nối tiếp nhau là T(n)=O(max(f(n),g(n))) .

Ví dụ: Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu

READ(x) tốn một hằng thời gian hay O(1).Vậy thời gian thực hiện cả hai lệnh trên

nối tiếp nhau là O(max(1,1))=O(1).

3.4.2. Qui tắc nhân

Nếu T₁(n) và T₂(n) là thời gian thực hiện của hai đoạn chương trình P₁và P₂

và T₁(n) = O(f(n)), T₂(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương

trình đó lồng nhau là T(n) = O(f(n).g(n)).

3.4.3. Qui tắc tổng quát để phân tích một chương trình:

- Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1);

- Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui

tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong

chuỗi lệnh;

- Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN

hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện

- 13 -

là O(1);

- Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực

hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian

thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.

Ví dụ: Tính thời gian thực hiện của thủ tục sắp xếp “nổi bọt”

int Bubble(int a[], int n) {

for(int i=1;i<=n-1;i++)

for(int j=0;j<n-i;j++)

if(a[j]>a[j+1] {

// {1}

// {2}

// {3}

// {4}

// {5}

// {6}

int temp := a[j];

a[j] := a[j+1];

a[j+1] := temp;

}

Về giải thuật sắp xếp nổi bọt, chúng ta sẽ bàn kĩ hơn trong chương sau. Ở đây,

chúng ta chỉ quan tâm đến độ phức tạp của giải thuật.

Ta thấy toàn bộ chương trình chỉ gồm một lệnh lặp {1}, lồng trong lệnh {1}

là lệnh {2}, lồng trong lệnh {2} là lệnh {3} và lồng trong lệnh {3} là 3 lệnh nối tiếp

nhau {4}, {5} và {6}. Chúng ta sẽ tiến hành tính độ phức tạp theo thứ tự từ trong ra.

Trước hết, cả ba lệnh gán {4}, {5} và {6} đều tốn O(1) thời gian, việc so sánh

a[j-1] > a[j] cũng tốn O(1) thời gian, do đó lệnh {3} tốn O(1) thời gian.

Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-

i).1) = O(n-i).

Vòng lặp {1} lặp có i chạy từ 1 đến n-1 nên thời gian thực hiện của vòng lặp

n1

n(n 1)

{1} và cũng là độ phức tạp của giải thuật là:T(n) = (n  i) 

= O(n²)



2

i1

Chú ý: Trong trường hợp vòng lặp không xác định được số lần lặp thì chúng

ta phải lấy số lần lặp trong trường hợp xấu nhất.

4. Một số giải thuật cơ bản

4.1. Hoán vị hai phần tử

- Dùng biến trung gian:

void swap(int &a, int &b){

int tam;

tam = a;

a = b;

b = tam;

}

- 14 -

Cách này đơn giản dễ cài đặt tuy nhiên tiêu tốn thêm bộ nhớ do khai báo và

sử dụng biến trung gian để lưu trữ các giá trị.

- Sử dụng hai phép toán + và -:

void swap(int &a, int &b){

a = a + b;

b = a - b;

a = a - b;

}

Cách này không tốn bộ nhớ do chỉ phải sử dụng các phép toán + và -, tuy

nhiên có nhược điểm là dễ gây tràn bộ nhớ.

- Sử dụng toán tử XOR:

void swap(int &a, int &b){

a = a ^ b;

b = a ^ b;

a = a ^ b;

}

Cách này sẽ nhanh nhất vì chỉ sử dụng phép toán tiền định của máy tính.

4.2. Tìm số lớn nhất, nhỏ nhất

- Phát biểu bài toán:

Tìm số lớn nhất và nhỏ nhất trong dãy các chữ số

- Giải thuật:

Bắt đầu, ta gán max, min bằng giá trị đầu tiên trong mảng. So sánh lần lượt

maxvà minvới các số tương ứng trong mảng. Nếu có một số lớn hơn maxhoặc có

một số nhỏ hơn minta gán maxhoặc minbằng giá trị mới.

Max_Min_Element (numbers[], n) {

max = numbers[0];

min = numbers[0];

for (i = 1; i < n; i ++)

if (numbers[i] > max)

max = numbers[i];

if (numbers[i] < min)

min = numbers[i];

return (max, min);

}

- Độ phức tạp:

Số các phép so sánh trong giải thuật là 2n-2, các phép so sánh có thể giảm

xuống nếu ta sử dụng kỹ thuật chia để trị.

- 15 -

4.3. Đệ quy

4.3.1. Khái niệm

Đệ qui là một khái niệm cơ bản trong toán học và khoa học máy tính. Một đối

tượng được gọi là đệ qui nếu nó hoặc một phần của nó được định nghĩa thông qua

khái niệm về chính nó. Một số ví dụ điển hình về việc định nghĩa bằng đệ qui là:

1- Định nghĩa số tự nhiên:

- 0 là số tự nhiên;

- Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên.

Như vậy, bắt đầu từ phát biểu “0 là số tự nhiên”, ta suy ra 0+1=1 là số tự

nhiên. Tiếp theo 1+1=2 là số tự nhiên, v.v.

2- Định nghĩa xâu ký tự bằng đệ qui:

- Xâu rỗng là một xâu ký tự;

- Một chữ cái bất kỳ ghép với một xâu sẽ tạo thành một xâu mới.

Từ phát biểu “Xâu rỗng là một xâu ký tự”, ta ghép bất kỳ một chữ cái nào với

xâu rỗng đều tạo thành xâu ký tự. Như vậy, chữ cái bất kỳ có thể coi là xâu ký tự.

Tiếp tục ghép một chữ cái bất kỳ với một chữ cái bất kỳ cũng tạo thành một xâu ký

tự, v.v.

3- Định nghĩa hàm giai thừa, n!.

- Khi n=0, định nghĩa 0!=1;

- Khi n>0, định nghĩa n!=(n-1)!×n.

Như vậy, khi n=1, ta có 1!=0!×1 = 1×1=1. Khi n=2, ta có 2!=1!×2=1×2=2,

v.v.

Trong lĩnh vực lập trình, một chương trình máy tính gọi là đệ qui nếu trong

chương trình có lời gọi chính nó. Điều này, thoạt tiên, nghe có vẻ hơi vô lý. Một

chương trình không thể gọi mãi chính nó, vì như vậy sẽ tạo ra một vòng lặp vô hạn.

Trên thực tế, một chương trình đệ qui trước khi gọi chính nó bao giờ cũng có một

thao tác kiểm tra điều kiện dừng. Nếu điều kiện dừng thỏa mãn, chương trình sẽ

không gọi chính nó nữa, và quá trình đệ qui chấm dứt. Trong các ví dụ ở trên, ta đều

thấy có các điểm dừng. Chẳng hạn, trong ví dụ thứ nhất, nếu k = 0 thì có thể suy

ngay k là số tự nhiên, không cần tham chiếu xem k-1 có là số tự nhiên hay không.

Nhìn chung, các chương trình đệ qui đều có các đặc điểm sau:

- Chương trình này có thể gọi chính nó.

- Khi chương trình gọi chính nó, mục đích là để giải quyết một vấn đề tương

tự, nhưng nhỏ hơn.

- 16 -

- Vấn đề nhỏ hơn này, cho tới một lúc nào đó, sẽ đơn giản tới mức chương

trình có thể tự giải quyết được mà không cần gọi tới chính nó nữa.

Khi chương trình gọi tới chính nó, các tham số, hoặc khoảng tham số, thường

trở nên nhỏ hơn, để phản ánh một thực tế là vấn đề đã trở nên nhỏ hơn, dễ hơn. Khi

tham số giảm tới mức cực tiểu, một điều kiện so sánh được kiểm tra và chương trình

kết thúc, chấm dứt việc gọi tới chính nó.

Ưu điểm của chương trình đệ qui cũng như định nghĩa bằng đệ qui là có thể

thực hiện một số lượng lớn các thao tác tính toán thông qua một đoạn chương trình

ngắn gọn (thậm chí không có vòng lặp, hoặc không tường minh để có thể thực hiện

bằng các vòng lặp) hay có thể định nghĩa một tập hợp vô hạn các đối tượng thông

qua một số hữu hạn lời phát biểu. Thông thường, một chương trình được viết dưới

dạng đệ qui khi vấn đề cần xử lý có thể được giải quyết bằng đệ qui.

Tức là vấn đề cần giải quyết có thể đưa được về vấn đề tương tự, nhưng đơn

giản hơn. Vấn đề nàylại được đưa về vấn đề tương tự nhưng đơn giản hơn nữa…,

cho đến khi đơn giản tới mức có thể trực tiếp giải quyết được ngay mà không cần

đưa về vấn đề đơn giản hơn nữa.

- Điều kiện để có thể viết một chương trình đệ qui

Như đã nói ở trên, để chương trình có thể viết dưới dạng đệ qui thì vấn đề cần

xử lý phải được giải quyết một cách đệ qui. Ngoài ra, ngôn ngữ dùng để viết chương

trình phải hỗ trợ đệ qui.

Để có thể viết chương trình đệ qui chỉ cần sử dụng ngôn ngữ lập trình có hỗ

trợ hàm hoặc thủ tục, nhờ đó một thủ tục hoặc hàm có thể có lời gọi đến chính thủ

tục hoặc hàm đó. Các ngôn ngữ lập trình thông dụng hiện nay đều hỗ trợ kỹ thuật

này, do vậy vấn đề công cụ để tạo các chương trình đệ qui không phải là vấn đề cần

phải xem xét. Tuy nhiên, cũng nên lưu ý rằng khi một thủ tục đệ qui gọi đến chính

nó, một bản sao của tập các đối tượng được sử dụng trong thủ tục này như các biến,

hằng, các thủ tục con, .v.v. cũng được tạo ra. Do vậy, nên hạn chế việc khai báo và

sử dụng các đối tượng này trong thủ tục đệ qui nếu không cần thiết nhằm tránh lãng

phí bộ nhớ, đặc biệt đối với các lời gọi đệ qui được gọi đi gọi lại nhiều lần. Các đối

tượng cục bộ của 1 thủ tục đệ qui khi được tạo ra nhiều lần, mặc dù có cùng tên,

nhưng do khác phạm vi nên không ảnh hưởng gì đến chương trình. Các đối tượng

đó sẽ được giải phóng khi thủ tục chứa nó kết thúc.

Nếu trong một thủ tục có lời gọi đến chính nó thì ta gọi đó là đệ qui trực tiếp.

Còn trongtrường hợp một thủ tục có một lời gọi thủ tục khác, thủ tục này lại gọi đến

thủ tục ban đầu thì được gọi là đệ qui gián tiếp. Như vậy, trong chương trình khi

nhìn vào có thể không thấy ngay sự đệ qui, nhưng khi xem xét kỹ hơn thì sẽ nhận

- 17 -

ra.

- Khi nào không nên sử dụng đệ qui

Trong nhiều trường hợp, một chương trình có thể viết dưới dạng đệ qui. Tuy

nhiên, đệ qui không hẳn đã là giải pháp tốt nhất cho vấn đề. Nhìn chung, khi chương

trình có thể viết dưới dạng lặp hoặc các cấu trúc lệnh khác thì không nên sử dụng đệ

qui.

Lý do thứ nhất là, như đã nói ở trên, khi một thủ tục đệ qui gọi chính nó, tập

các đối tượngđược sử dụng trong thủ tục này như các biến, hằng, cấu trúc .v.v sẽ

được tạo ra. Ngoài ra, việc chuyển giao điều khiển từ các thủ tục cũng cần lưu trữ

các thông số dùng cho việc trả lại điều khiển cho thủ tục ban đầu.

Lý do thứ hai là việc sử dụng đệ qui đôi khi tạo ra các tính toán thừa, không

cần thiết do tính chất tự động gọi thực hiện thủ tục khi chưa gặp điều kiện dừng của

đệ qui. Để minh họa cho điều này, chúng ta sẽ xem xét một ví dụ, trong đó cả đệ qui

và lặp đều có thể được sử dụng. Tuy nhiên, ta sẽ phân tích để thấy sử dụng đệ qui

trong trường hợp này gây lãng phí bộ nhớ và các tính toán không cần thiết như thế

nào.

4.3.2 Thiết kế giải thuật đệ quy

- Chương trình tính hàm n!

Theo định nghĩa đã trình bày ở phần trước, n! = 1 nếu n=0, ngược lại, n! = (n-

1)! * n.

int Giaithua (int n){

if (n==0)

return 1;

else

return giaithua(n-1) * n;

}

Trong chương trình trên, điểm dừng của thuật toán đệ qui là khi n=0. Khi đó,

giá trị của hàm giaithua(0) có thể tính được ngay lập tức mà không cần gọi hàm đệ

qui khác. Nếu điều kiện dừng không thỏa mãn, sẽ có một lời gọi đệ qui hàm giai

thừa với tham số là n-1, nhỏ hơn tham số ban đầu 1 đơn vị (tức là bài toán tính n! đã

được qui về bài toán đơn giản hơn là tính (n-1)!).

- Thuật toán Euclid tính ước số chung lớn nhất của 2 số nguyên dương

Ước số chung lớn nhất (USCLN) của 2 số nguyên dương m, n là 1 số k lớn

nhất sao cho mvà n đều chia hết cho k. Một phương pháp đơn giản nhất để tìm

USCLN của m và n là duyệt từ số nhỏ hơn trong 2 số m, n cho đến 1, ngay khi gặp

số nào đó mà m và n đều chia hết cho nó thì đó chính là USCLN của m, n. Tuy nhiên,

- 18 -

phương pháp này không phải là cách tìm USCLN hiệu quả.

Cách đây hơn 2000 năm, Euclid đã phát minh ra một giải thuật tìm USCLN

của 2 số nguyên dương m, n rất hiệu quả. Ý tưởng cơ bản của thuật toán này cũng

tương tự như ý tưởng đệ qui, tức là đưa bài toán về 1 bài toán đơn giản hơn. Cụ thể,

giả sử m lớn hơn n, khi đó việc tính USCLN của m và n sẽ được đưa về bài toán tính

USCLN của (m % n) và n vì USCLN(m, n) = USCLN(m % n, n).

Thuật toán được cài đặt như sau:

int USCLN(int m, int n) {

if (n==0)

return m;

else

return USCLN(n, m % n);

}

Điểm dừng của thuật toán là khi n=0. Khi đó đương nhiên là USCLN của m

và 0 chính làm, vì 0 chia hết cho mọi số. Khi n khác 0, lời gọi đệ qui USCLN(n, m%

n) được thực hiện. Chú ý rằng ta giả sử m >= n trong thủ tục tính USCLN, do đó,

khi gọi đệ qui ta gọi USCLN (n, m % n) để đảm bảo thứ tự các tham số vì n bao giờ

cũng lớn hơn phần dư của phép m cho n. Sau mỗi lần gọi đệ qui, các tham số của

thủ tục sẽ nhỏ dần đi, và sau 1 số hữu hạn lời gọi tham số nhỏ hơn sẽ bằng 0. Đó

chính là điểm dừng của thuật toán.

4.4. Chia để trị

Ý tưởng cơ bản của các thuật toán dạng chia để trị là phân chia bài toán ban

đầu thành 2 hoặc nhiều bài toán con có dạng tương tự và lần lượt giải quyết từng bài

toán con này. Các bài toán con này được coi là dạng đơn giản hơn của bài toán ban

đầu, do vậy có thể sử dụng các lời gọi đệ qui để giải quyết. Thông thường, các thuật

toán chia để trị chia bộ dữ liệu đầu vào thành 2 phần riêng rẽ, sau đó gọi 2 thủ tục

đệ qui để với các bộ dữ liệu đầu vào là các phần vừa được chia.

Một ví dụ điển hình của giải thuật chia để trị là QuickSort, một giải thuật sắp

xếp nhanh. Ý tưởng cơ bản của giải thuật này như sau:

Giả sử ta cần sắp xếp 1 dãy các số theo chiều tăng dần. Tiến hành chia dãy đó

thành 2 nửa sao cho các số trong nửa đầu đều nhỏ hơn các số trong nửa sau. Sau đó,

tiến hành thực hiện sắp xếp trên mỗi nửa này. Rõ ràng là sau khi mỗi nửa đã được

sắp, ta tiến hành ghép chúng lại thì sẽ có toàn bộ dãy được sắp. Chi tiết về giải thuật

QuickSort sẽ được trình bày trong chương Sắp xếp.

Tiếp theo, chúng ta sẽ xem xét một bài toán cũng rất điển hình cho lớp bài

toán được giải bằng giải thuật đệ qui chia để trị.

Bài toán tháp Hà nội

- 19 -