Bài giảng chương 1: Tổng quan về cấu trúc dữ liệu

Ch ng 1:ươ T NG QUAN V C U TRÚC D LI UỔ Ề Ấ Ữ Ệ ----o0o---- 1.1. Khái ni m v c u trúc d li u.ệ ề ấ ữ ệ C u trúc d li u (CTDL) là m t cách t ch c d li u c a bài toán. CTDL có th doấ ữ ệ ộ ổ ứ ữ ệ ủ ể ngôn ng l p trình đ nh nghĩa tr c ho c có th do ng i s d ng đ nh nghĩa.ữ ậ ị ướ ặ ể ườ ử ụ ị C u trúc d li u t t thì thu t toán x lý bài toán m i t i u. Chính vì v y, Niklausấ ữ ệ ố ậ ử ớ ố ư ậ wirth đã t ng k t:ổ ế “C u trúc d li u + thu t toán = Ch ng trình”ấ ữ ệ ậ ươ . Cách bi u di n t i u m t c u trúc d li u trong b nh đ c g i là c u trúc l u trể ễ ố ư ộ ấ ữ ệ ộ ớ ượ ọ ấ ư ữ (storage structure). Có th có nhi u c u trúc l u tr cho cùng m t c u trúc d li u.ể ề ấ ư ữ ộ ấ ữ ệ C u trúc d li u t ng ng v i b nh g i là l u tr trong hay t ng ng v i b nhấ ữ ệ ươ ứ ớ ộ ớ ọ ư ữ ươ ứ ớ ộ ớ ngoài g i là l u tr ngoài.ọ ư ữ Thông th ng m t ki u d li u đ c đ nh nghĩa nh sau:ườ ộ ể ữ ệ ượ ị ư M t ki u d li u T là m t c p T = trong đó:ộ ể ữ ệ ộ ặ - V (value) : Là m t t p các tr mà m t bi n có ki u T nh n đ c.ộ ậ ị ộ ế ể ậ ượ - O (Operator) : Là t p h p các thao tác trên V.ậ ợ Ví d :ụ a. T ≡ Integer = V={-32768,...,32767} ; O={+,-,*,/,mod,div,xor,,...} b. T ≡ Boolean = V={True, False}; O = { And, Or, Xor, Not, , =,…} M t c u trúc d li u là m t ki u d li u đ c xây d ng t nh ng ki u d li u đãộ ấ ữ ệ ộ ể ữ ệ ượ ự ừ ữ ể ữ ệ bi t, trong tr ng h p này cho ta m t CTDL t ng ng v i m t ki u d li u đã cho.ế ườ ợ ộ ươ ứ ớ ộ ể ữ ệ 1.2. Các c u trúc d li u căn b n.ấ ữ ệ ả 1.2.1. Các ki u d li u căn b n.ể ữ ệ ả - Ki u Integerể (nguyên – 2 byte, -32768 .. 32767). G m t p h p con các s nguyên. T t cồ ậ ợ ố ấ ả các phép toán trên d li u integer đ u tuân th các qui t c s h c. Các toán t chu n g mữ ệ ề ủ ắ ố ọ ử ẩ ồ b n phép toán s h c c b n: c ng (+), tr (-), nhân (*), chia nguyên (div).ố ố ọ ơ ả ộ ừ - Ki u Real ể (th c – 6 byte,2.9E-39 .. 1.7E38). G m t p h p con c a các s th c, các toánự ồ ậ ợ ủ ố ự t chu n g m b n phép toán s h c c b n là: công (+), tr (-), nhân (/).ử ẩ ồ ố ố ọ ơ ả ừ - Ki u Boolean ể (lu n lý – 1 bit). G m hai giá tr luân lý ậ ồ ị true (đúng) và false (sai). Các toán t lu n lý g m ba phép toán c b n: not (ph đ nh), and (và) và or (hay).ử ậ ồ ơ ả ủ ị Các phép toán so sánh cho k t qu là m t giá tr lu n lý. Các phép toán so sánhế ả ộ ị ậ g m:ồ = b ngằ khác b ng (khác)ằ < nh h nỏ ơ <= nh h n ho c b ngỏ ơ ặ ằ 1 > l n h nớ ơ >= l n h n ho c b ngớ ơ ặ ằ - Ki u charể ( kí t – 1 byte): G m t p h p các kí t in đ c. Các kí t th ng dùng là:ự ồ ậ ợ ự ượ ự ườ + Ki u char g m 26 ch Latin ((‘A’<=x) and (x<=’Z’)), 10 ký s ( 0 .. 9) và m t sể ồ ữ ố ộ ố ký t đ c bi t, ký t tr ng.ự ặ ệ ự ắ - Ki u li t kêể ệ (Enuerated Types) Ki u li t kê g m m t t p h p các giá tr b ng cách li t kê các ể ệ ồ ộ ậ ợ ị ằ ệ danh hi uệ (identifier) ch đ nh các giá tr này. Th t c a các ki u li t kê đ c đ nh nghĩa nh sau:ỉ ị ị ứ ự ủ ể ệ ượ ị ư Type T = (c1,c2,…, cn) trong đó c1,c2,…, cn là các danh hi u ch đ nh các giá tr c a ki uệ ỉ ị ị ủ ể li t kê.ệ Ví d : ụ Type shape = (rectange, square, ellipse, circle) - Ki u mi n conể ề (Subrange Types) là tr ng h p m t bi n có giá tr ch n m trong m tườ ợ ộ ế ị ỉ ằ ộ kho ng xác đ nh nào đó c a m t ki u. Đi u này có th đ c bi u di n b ng cách đ nhả ị ủ ộ ể ề ể ượ ể ễ ằ ị nghĩa bi n thu c ki u mi n con theo d ng:ế ộ ể ề ạ Type T= min … max - Ki u chu iể ỗ (string). G m m t t p h p các kí t . Các chu i kí t này đ c ghi trong haiồ ộ ậ ợ ự ỗ ự ượ d u nháy đ n (‘) và có t i đa 255 ký t . S ký t c a chu i đ c g i là chi u dài c aấ ơ ố ự ố ự ủ ỗ ượ ọ ề ủ chu i, đ c khai báo nh sau:ỗ ượ ư Var s : string[10] ; 1.2.2. Các ki u d li u có c u trúc.ể ữ ệ ấ a. Ki u m ng.ể ả M ng là m t b ng ch a d li u có cùng ki u, trên các hàng c t, giá tr c a d li uả ộ ả ứ ữ ệ ể ộ ị ủ ữ ệ đ c xác đ nh theo ch s hàng, c t. Có hai lo i m ng: M t chi u, hai chi u.ượ ị ỉ ố ộ ạ ả ộ ề ề Bao g m có tên c a m ng và ch s t ng ngồ ủ ả ỉ ố ươ ứ Ví d :ụ M ng m t chi u a(n) v i n là s nguyên nào đó, cho xác đ nh s ph n t c aả ộ ề ớ ố ị ố ầ ử ủ m ng, ph n t c a m ng đ c xác đ nh theo ch s , ch ng h n ph n t th 3 c a m ngả ầ ử ủ ả ượ ị ỉ ố ẳ ạ ầ ử ứ ủ ả a ta ghi a[3] (d u ngo c vuông).ấ ặ M ng hai chi u a(n,m) th ng có nxm ph n t , g m có n hàng, m c t, m t ph n tả ề ườ ầ ử ồ ộ ộ ầ ử th i,j nào đó có nghĩa là ph n t hàng th i, c t th j.ứ ầ ử ở ứ ộ ứ * M ng m t chi u.ả ộ ề - Cú pháp: + Khai báo gián ti p:ế Ki u TYPE = Array[ Ch s ] OF ;ể ả ỉ ố ể ữ ệ VAR :;ế ả ể ả + Khai báo tr c ti p:ự ế VAR : ARRAY [ch s ] OF ế ả ỉ ố ể ữ ệ ; Chú ý: Ch s trong khai báo đ i v i Pascal ph i đ c xác đ nh tr c khai báo h ngỉ ố ố ớ ả ượ ị ướ ở ằ ho c ghi c th .ặ ụ ể 2 * M ng hai chi u.ả ề - Cú pháp: + Khai báo gián ti p:ế TYPE = ARRAY [ch s 1, ch s 2] OF ; ể ả ỉ ố ỉ ố ể ữ ệ VAR :;ế ả ể ả + Khai báo tr c ti p:ự ế VAR : ARRAY [ch s 1, ch s 2] OF ; ế ả ỉ ố ỉ ố ể ữ ệ Ví d :ụ TYPE Mangnguyen = Array[1..100] of Integer; Matrix = Array[1..10,1..10] of Integer; MangKytu = Array[Byte] of Char; VAR A: Mangnguyen; M: Matrix; C: MangKytu; Ho c:ặ VAR A: Array[1..100] of Integer; C: Array[Byte] of Char; b. Ki u xâu ký t .ể ự Chúng ta gọi kiểu dữ liệu có giá trị là tập những kí tự là kiểu xâu kí tự hay nói một cách ngắn gọn là kiểu xâu. Pascal có từ khoá STRING để người dùng khai báo cho dữ liệu có giá trị là tập những kí tự. Ví dụ ta khai báo biến A có kiểu là tập những kí tự như sau: VAR A : STRING ; máy dành cho biến A có thể lưu giữ được một tập có không quá 255 kí tự. Hằng văn bản phải để trong cặp dấu nháy cao (‘). * Khai báo. TYPETênKi u = STRING[Max];ể VAR Tên bi n : TênKi u;ế ể ho c khai báo bi n tr c ti p:ặ ế ự ế VAR Tên bi n : STRING[Max];ế Trong đó Max là s ký t t i đa có th ch a trong chu i (Max ố ự ố ể ứ ỗ ∈ [0,255]). N u không cóế khai báo [Max] thì s ký t m m c đ nh trong chu i là 255.ố ự ặ ặ ị ỗ Ví d :ụ Type Hoten = String[30]; St80 = String[80]; Var Name : Hoten; Line : St80; St : String; {St có t i đa là 255 ký t }ố ự 3 * Truy xu t ph n t .ấ ầ ử - Có th s d ng các th t c xu t nh p Write, Writeln, Readln đ truy xu t các bi nể ử ụ ủ ụ ấ ậ ể ấ ế ki u String. ể - Đ truy xu t đ n ký t th k c a xâu ký t , ta s d ng cú pháp sau: ể ấ ế ự ứ ủ ự ử ụ Tênbi n[k]ế . * Các th t c và hàm trên xâu ký t ủ ụ ự - Hàm l y chi u dài c a xây ký tấ ề ủ ự LENGTH(St : String):Integer; - Hàm COPY(St : String; Pos, Num: Byte): String; L y ra m t xâu con t trong xâu St có đ dài Num ký t b t đ u t v trí Pos .ấ ộ ừ ộ ự ắ ầ ừ ị - Hàm POS(SubSt, St :String):Byte; Ki m tra xâu con SubSt có n m trong xâu St hay không? N u xâu SubSt n m trong xâu Stể ằ ế ằ thì hàm tr v v trí đ u tiên c a xâu con SubSt trong xâu St, ng c l i hàm tr v giá trả ề ị ầ ủ ượ ạ ả ề ị 0. - Th t c DELETE(Var St:String; Pos, Num: Byte);ủ ụ Xoá trong xâu St Num ký t b t đ u t v trí Pos.ự ắ ầ ừ ị - Th t c INSERT(SubSt: String; Var St: String; Pos: Byte);ủ ụ Chèn xâu SubSt vào xâu St b t đ u t i v trí Pos.ắ ầ ạ ị - Th t c STR(Num; Var St:String);ủ ụ Đ i s nguyên hay th c Num thành d ng xâu ký t , k t qu l u vào bi n St.ổ ố ự ạ ự ế ả ư ế - Th t c VAL(St:String; Var Num; Var Code:Integer);ủ ụ Đ i xâu s St thành s và gán k t qu l u vào bi n Num. N u vi c chuy n đ i thànhổ ố ố ế ả ư ế ế ệ ể ổ công thì bi n Code có giá tr là 0, ng c l i bi n Code có giá tr khác 0 (v trí c a l i).ế ị ượ ạ ế ị ị ủ ỗ c. Ki u b n ghi.ể ả Nh ta đã bi t các ki u d li u đã có, m i bi n thu c m t lo i ki u nào đó thì giá trư ế ể ữ ệ ỗ ế ộ ộ ạ ể ị c a chúng ch thu c m t ki u đó: Ch ng h n ki u s nguyên, ki u m ng…Trong khi đóủ ỉ ộ ộ ể ẳ ạ ể ố ể ả ki u b n ghi có th coi nh s m r ng các khái ni m bi n và m ng, nó cho phép l u trể ả ể ư ự ở ộ ệ ế ả ư ữ và x lý các d ng thông tin ph c t p h n. RECORD là m t t p h p các bi n, các m ngử ạ ứ ạ ơ ộ ậ ợ ế ả và đ c hi n th b ng m t tên duy nh t.ượ ể ị ằ ộ ấ * Khai báo. TYPETênKi u = RECORDể Field1 : Ki u1;ể Field2 : Ki u2;ể ... FieldN: Ki uN;ể END; VAR Bi n : TênKi u;ế ể 4 Ví dụ: TYPE HocSinh = Record Hoten : String[20]; Tuoi : Integer; DiemTB : real; End; VAR HS : HocSinh; 1.2.3. Ki u con tr .ể ỏ * Khai báo Type = ^ ;ể ỏ ể ủ ế ộ Var :;ế ể ỏ Ví d 1ụ : Type TroNguyen = ^integer; Var p, q: TroNguyen; Sau khai báo này các bi n p và q là các bi n con tr có th tr đ n các bi n đ ng cóế ế ỏ ể ỏ ế ế ộ ki u integer. Ch ng trình s c p phát 4 byte cho m i bi n con tr . Còn vùng nh c aể ươ ẽ ấ ỗ ế ỏ ớ ủ các bi n đ ng ch a đ c c p phát.ế ộ ư ượ ấ Ví d 2ụ : Type TroSv = ^ Sinhvien; Sinhvien = Record Hoten: String[20]; Diem: real; Tiep: TroSv; End; Var p: TroSv; Trong ví d này, p là bi n tr có th tr đ n các b n ghi có ki u Sinhvien, trongụ ế ỏ ể ỏ ế ả ể b n ghi này l i có tr ng Tiep là m t bi n tr có th tr đ n bi n đ ng khác cũng cóả ạ ườ ộ ế ỏ ể ỏ ế ế ộ ki u Sinhvien.ể * Làm vi c v i bi n đ ngệ ớ ế ộ - C p phát vùng nhấ ớ Dùng th t c New theo cú pháp:ủ ụ New();ế ỏ 5 - Gi i phóng vùng nhả ớ Dùng th t c ủ ụ Dispose(p); Trong đó p là m t bi n con tr . Th t c Dispose cho phép tr l i b nh đ ng đãộ ế ỏ ủ ụ ả ạ ộ ớ ộ đ c c p phát b i th t c New.ượ ấ ở ủ ụ 1.3. Thu t toán và đánh giá đ ph c t p thu t toán ậ ộ ứ ạ ậ . 1.3.1. Thu t toán.ậ a. Khái ni m thu t toán (hay Gi i thu t).ệ ậ ả ậ Thu t toán hay gi i thu t là m t h th ng ch c ch và rõ ràng các quy t c nh m xácậ ả ậ ộ ệ ố ặ ẽ ắ ằ đ nh m t dãy các thao tác trên nh ng đ i t ng, sao cho sau m t s h u h n b c th cị ộ ữ ố ượ ộ ố ữ ạ ướ ự hi n các thao tác thì cho k t qu .ệ ế ả b. Các đ c tr ng c a gi i thu t.ặ ư ủ ả ậ * Tính xác đ nhị Gi i thu t bao g m các b c rõ ràng. Trong cùng m t đi u ki n thì k t qu c a m iả ậ ồ ướ ộ ề ệ ế ả ủ ỗ b c là xác đ nh.ướ ị * Tính h u h n d ngữ ạ ừ Gi i thu t sau m t s h u h n b c thì cho k t qu .ả ậ ộ ố ữ ạ ướ ế ả * Tính đúng đ n.ắ Sau khi th c hi n các b c c a gi i thu t ph i cho đ c k t qu mong mu n, k tự ệ ướ ủ ả ậ ả ượ ế ả ố ế qu đó đ c xác đ nh theo đ nh nghĩa có tr c.ả ượ ị ị ướ * Tính ph d ngổ ụ Gi i thu t ph i gi i quy t đ c cho m t l p bài toán.ả ậ ả ả ế ượ ộ ớ * Tính có đ i l ng vào và raạ ượ B t đ u m t gi i thu t là vi c nh n d li u vào (Input) – k t thúc gi i thu t là m tắ ầ ộ ả ậ ệ ậ ữ ệ ế ả ậ ộ s k t qu (d li u ra Output).ố ế ả ữ ệ * Tính hi u qu .ệ ả Tính hi u qu c a m t gi i thu t đ c đánh giá d a trên các tiêu chu n sau:ệ ả ủ ộ ả ậ ượ ự ẩ - Dung l ng b c n thi tượ ộ ầ ế - S l ng phép tính c n th c hi n.ố ượ ầ ự ệ - Th i gian c n thi t đ ch y.ờ ầ ế ể ạ - D hi u và d cài đ t.ễ ể ễ ặ c. Bi u di n thu t toán ể ễ ậ Th ng có hai cách bi u di n m t thu t toán, cách th nh t là mô t các b c th cườ ể ễ ộ ậ ứ ấ ả ướ ự hi n c a thu t toán, cách th hai là s d ng s đ gi i thu t.ệ ủ ậ ứ ử ụ ơ ồ ả ậ - Mô t các b c th c hi n.ả ướ ự ệ Đ bi u di n thu t toán ng i ta mô t chính xác các b c th c hi n c a thu t toán,ể ể ễ ậ ườ ả ướ ự ệ ủ ậ ngôn ng dùng đ mô t thu t toán có th là ngôn ng t nhiên ho c m t ngôn ng laiữ ể ả ậ ể ữ ự ặ ộ ữ ghép gi a ngôn ng t nhiên v i m t ngôn ng l p trình nào đó g i là các đo n gi mãữ ữ ự ớ ộ ữ ậ ọ ạ ả 6 l nh.ệ Ví d 1:ụ mô t thu t toán tìm c s chung l n nh t c a hai s nguyên.ả ậ ướ ố ớ ấ ủ ố Input: Hai s nguyên a, b.ố Output: c s chung l n nh t c a a, b.Ướ ố ớ ấ ủ Thu t toán:ậ B c 1: N u a=b th USCLN(a, b)=a.ướ ế ́ B c 2: N u a > b th tm USCLN c a a-b và b, quay l i b c 1;ướ ế ́ ́ ủ ạ ướ B c 3: N u a < b th tm USCLN c a a và b-a, quay l i b c 1;ướ ế ́ ́ ủ ạ ướ Ví d 2:ụ Đ gi i ph ng trình b c hai axể ả ươ ậ 2 + bx +c = 0, ta có th mô t thu t toán b ngể ả ậ ằ ngôn ng li t kê nh sau:ữ ệ ư B c 1: Xác đ nh các h s a,b,c.ướ ị ệ ố B c 2 :Ki m tra xem các h s a,b,c có khác 0 hay không ?ướ ể ệ ố N u a=0 quay l i th c hi n b c 1.ế ạ ự ệ ướ B c 3: Tính bi u th c ướ ể ứ = b2 – 4*a*c. B c 4:N u ướ ế ∆ <0 thông báo ph ng trình vô nghi m và chuy n sang b c 8. ươ ệ ể ướ B c 5:N u ướ ế ∆=0,tính x1=x2= a b *2 − và chuy n sang b c 7.ể ướ B c 6: Tính xướ 1= a b *2 ∆−− , x2= a b *2 ∆+− và chuy n sang b c 7.ể ướ B c 7: Thông báo các nghi m xướ ệ 1 , x2 . B c 8: K t thúc thu t toán.ướ ế ậ - S d ng l uử ụ ư đ gi i thu t.ồ ả ậ S d ng các k hi u hnh kh i c b n đ t o thành m t mô t mang tính hnh th cử ụ ư ệ ́ ố ơ ả ể ạ ộ ả ́ ứ (cách này r ràng h n so v i vi c mô t các b c th c hi n thu t toán).ơ ơ ớ ệ ả ướ ự ệ ậ 7 Nh p, Xu tậ ấ B t đ uắ ầ K t ế thúc Câu l nhệ Đi u ề ki nệ 1 2 3 4 5 Đúng Sai Kh i 1:ố Kh i b t đ u thu t toán, ch có duy nh t m t đ ng ra.ố ắ ầ ậ ỉ ấ ộ ườ Kh i 2:ố Kh i k t thúc thu t toán, có th có nhi u đ ng vào.ố ế ậ ể ề ườ Kh i 3:ố Th c hi n câu l nh (có th là m t ho c nhi u câu l nh); g m m t đ ng vào vàự ệ ệ ể ộ ặ ề ệ ồ ộ ườ m t đ ng ra.ộ ườ Kh i 4:ố R nhánh, ki m tra bi u th c đi u ki n (bi u th c Boolean), n u bi u th cẽ ể ể ứ ề ệ ể ứ ế ể ứ đúng thu t toán s đi theo nhánh Đúng (True), n u bi u th c sai thu t toán s đi theoậ ẽ ế ể ứ ậ ẽ nhánh Sai (False). Kh i 5:ố Các câu l nh nh p và xu t d li u.ệ ậ ấ ữ ệ d. Phân tích th i gian th c hi n gi i thu t.ờ ự ệ ả ậ M t gi i thu t cho m t l i gi i th a đáng đ i v i m t bài toán ph i th a:ộ ả ậ ộ ờ ả ỏ ố ớ ộ ả ỏ - Đúng. - Hi u qu .ệ ả Th c đo v tính hi u qu th ng là th i gian mà máy s d ng đ gi i quy t bàiướ ề ệ ả ườ ờ ử ụ ể ả ế toán, khi các giá tr đ u vào có m t kích th c xác đ nh. Th c đo th hai là dung l ngị ầ ộ ướ ị ướ ứ ượ b nh đòi h i đ th c hi n gi i thu t ng v i giá tr đ u vào có kích th c xác đ nh.ộ ớ ỏ ể ự ệ ả ậ ứ ớ ị ầ ướ ị S phân tích th i gian c n thi t đ gi i m t bài toán có kích th c nào đó, liênự ờ ầ ế ể ả ộ ướ quan đ n đ ph c t p th i gian c a gi i thu t. S phân tích b nh c n thi t c a máyế ộ ứ ạ ờ ủ ả ậ ự ộ ớ ầ ế ủ tính liên quan đ n đ ph c t p không gian c a gi i thu t.ế ộ ứ ạ ủ ả ậ S xem xét đ ph c t p không gian g n v i c u trúc d li u đ c dùng đ th cự ộ ứ ạ ắ ớ ấ ữ ệ ượ ể ự hi n gi i thu t. Trong ph n này ta xét đ n đ ph c t p th i gian.ệ ả ậ ầ ế ộ ứ ạ ờ Đ ph c t p th i gian là m t hàm t l v i kích th c d li u, ký hi u là T(n),ộ ứ ạ ờ ộ ỷ ệ ớ ướ ữ ệ ệ trong đó n là kích th c d li u vào.ướ ữ ệ Tuy nhiên T(n) không th bi u di n thành đ n v th i gian là giây, phút…(do cácể ể ễ ơ ị ờ máy tính có c u hình khác nhau, h th ng khác nhau…). M c dù v y, chúng ta hoàn toànấ ệ ố ặ ậ có th so sánh đ c d a vào các giá tr c a hàm. Ví d :ể ượ ự ị ủ ụ Gi i thu t 1: - Đ ph c t p th i gian Tả ậ ộ ứ ạ ờ 1(n) = an2 Gi i thu t : - Đ ph c t p th i gian Tả ậ ộ ứ ạ ờ 2(n) = kn Khi n l n rõ ràng là Tớ 1(n) >=T2(n). V y gi i thu t 1 ch m h n gi i thu t 2.ậ ả ậ ậ ơ ả ậ 1.3.2. Đánh giá đ ph c t p c a gi i thu t.ộ ứ ạ ủ ả ậ Gi s ta có hai gi i thu t P1 và P2 v i th i gian th c hi n t ng ng là T1(n) =ả ử ả ậ ớ ờ ự ệ ươ ứ 100n2 (v i t su t tăng là nớ ỷ ấ 2) và T2(n) = 5n 3(v i t su t tăng là nớ ỷ ấ 3). 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ì P2 sệ ơ ả ờ ụ ộ ướ ữ ệ ớ ẽ nhanh h n P1 (T2ư 20 thì ng c l i do s mũ c a 100nươ ạ ố ủ 2 nh h n s mũ c a 5nỏ ơ ố ủ 3 (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 P1 và P2 đ uế ườ ợ ờ ự ệ ủ ả ề không l n và s khác bi t gi a T1 và T2 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. ự ệ 8 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ộ ọ ộ ứ ạ ế ồ ạ ằ 0 sao cho T(n) ≤ Cf(n) v i m i n ≥ Nớ ọ 0 (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 1ụ : T(n)= (n+1) 2có t su t tăng là nỷ ấ 2 nên T(n)= (n+1)2 là O(n2) 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:ể ệ ộ ứ ạ ạ ườ ặ Đ ph c t p:ộ ứ ạ O(1) O(logn) O(n) O(nlogn) O(nb) O(bn), b>1 O(n!) Thu t ngậ ữ Đ ph c t p h ng s .ộ ứ ạ ằ ố Đ ph c t p logarit.ộ ứ ạ Đ ph c t p tuy n tính.ộ ứ ạ ế Đ ph c t p nlogn.ộ ứ ạ Đ ph c t p đa th c.ộ ứ ạ ứ Đ ph c t p hàm mũ.ộ ứ ạ Đ ph c t p n!.ộ ứ ạ 9 Xác đ nh đ ph c t p tính toánị ộ ứ ạ . * Quy t c c ng:ắ ộ Gi s T1(n) và T2(n) là th i gian th c hi n c a hai đo n ch ng trình P1 vàả ử ờ ự ệ ủ ạ ươ P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì th i gian th c hi n P1 r i P2 ti p theoờ ự ệ ồ ế s là:ẽ T1(n) + T2(n) = O(Max(f(n),g(n)). Ví d 1ụ : Trong m t ch ng trình có 3 b c th c hi n mà th i gian th c hi nộ ươ ướ ự ệ ờ ự ệ t ng b c l n l t là O(nừ ướ ầ ượ 2), O(n3) và O(nlog2n) thì th i gian th c hi n 2 b cờ ự ệ ướ đ u là:ầ O(max(n2,n3) = O(n3). Th i gian th c hi n ch ng trình s làờ ự ệ ươ ẽ : O(n3,nlog2n) = O(n3). - M t ng d ng khác c a quy t c này là n u g(n) ộ ứ ụ ủ ắ ế ≤ f(n) v i m i nớ ọ ≤ no thì O(f(n) = g(n)) cũng là O(f(n)). Ch ng h nẳ ạ : O(n4 + n2) = O(n4) và O(n+Log2n) = O(n). Ví d ụ 2: 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).ố ế * Quy t c nhânắ : N u T1(n) và T2(n) là th i gian th c hi n c a hai đo n ch ng trình P1và P2ế ờ ự ệ ủ ạ ươ và T1(n) = O(f(n)), T2(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)). 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 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 3ụ : 1. Câu l nh gán: x:=x+1 có th i gian th c hi n b ng c (h ng s ) nên đ c đánhệ ờ ự ệ ằ ằ ố ượ giá là O(1). 2. Câu l nh:ệ For i:=1 to n do x:=x+1; Có th i gian th c hi n gi i thu t là O(n.1) = O(n).ờ ự ệ ả ậ 3. Câu l nh:ệ For i:=1 to n do For j:=1 to n do x:=x+1; Có th i gian th c hi n gi i thu t đ c đánh giá là O(n.n) = O(nờ ự ệ ả ậ ượ 2) 4. Gi s có hàm đ qui:ả ử ệ Function Vidu(n:integer):Real; Begin If n=1 then Vidu:=K {1} Else Vidu:=K/(2*n-3)+Vidu(n-1). {2} End ; G i th i gian th c hi n phép gán {1} là a, th i gian th c hi n phép chi {2} làọ ờ ự ệ ờ ự ệ b thì : T(n) = b+T(n-1) = b+b+T(n-2) = b+b+...+T(1) T(n) = b(n-1)+a. L y C = Max(a,b) ấ ⇒ T(n) ≤ Cn, ∀n. V yậ T(n) là O(n). Ch ng 2: DANH SÁCHươ -----o0o----- 2.1. Đ nh nghĩa danh sách.ị Danh sách là m t t p h u h n các ph n t (element) aộ ậ ữ ạ ầ ử 1, a2, …, an, gi a cácữ ph n t có m i quan h t ng đ i: N u bi t ph n t aầ ử ố ệ ươ ố ế ế ầ ử i thì s đ nh đ c v tríẽ ị ượ ị ph n t aầ ử i+1. Nói cách khác h n, các ph n t thu c m t danh sách có th s p x pơ ầ ử ộ ộ ể ắ ế tuy n tính.ế Ví d 1: - Danh sách sinh viên là m t danh sách.ụ ộ - Ki u d li u m ng trong pascal là m t danh sách.ể ữ ệ ả ộ 2.2. Danh sách đ c.ặ 2.2.1. Đ nh nghĩa.ị Danh sách đ c là m t danh sách mà các ph n t đ c s p x p k ti p nhau trongặ ộ ầ ử ượ ắ ế ế ế b nh .ộ ớ 2.2.2. T ch c c u trúc d li u.ổ ứ ấ ữ ệ Ta bi u di n danh sách đ c là m t dãy n ph n tể ễ ặ ộ ầ ử a[1] a[2] ... a[n] Ta khai báo m t danh sách đ c là m t dãy s nguyên a[1], a[2],..., a[n] nh sau:ộ ặ