# Chuong 1. tong quan

• Published on
08-Jul-2015

• View
403

1

Transcript

1Chng 1: Tng quan1.1. Cc bc c bn khi gii mt bi ton tin hc1.2. Vai tr ca cu trc d liu v gii thut1.3. Cc cu trc d liu c bn1.4. nh gi phc tp gii thut1.5. Bi tp21.1. Cc bc c bn khi gii mt bi ton tin hc 3Cc bc c bn Khi tin hnh gii cc bi ton tin hc cn tin hnh cc bc c bn sau: 1. Xc nh bi ton2. Tm cu trc d liu3. Tm gii thut4. Lp trnh5. Kim th6. Ti u chng trnh4B1: Xc nh bi ton Vic xc nh bi ton tc l phi xc nh xem:1. Phi gii quyt vn g?2. Vi gi thit no cho?3. Li gii cn phi t nhng yu cu g? i khi nhng bi ton tin hc ng dng trong thc tch cn tm li gii tt ti mc no , thm ch l ti mc chp nhn c. Bi v li gii tt nht c th i hi qu nhiu thi gian v chi ph. V d: Gii phng trnh f(x) = 0 vi x l bin s, f(x) l 1 a thc ca x c bc 3.5B1: Xc nh bi ton Bi ton 1: Chia nhm tho lunMt lp hc c N sinh vin cng tham gia tho lun v mt vn , h mun chia thnh cc nhm v mi nhm tho lun ring v mt phn ca vn . Nhm c bao nhiu sinh vin th c a ra by nhiu kin. Nu ly mi nhm mt kin em ghp li th c mt b kin gii quyt vn . Hy tm cch chia sinh vin thnh cc nhm s b kin S thu c lln nht.V d: vi N = 7, kt qu l chia thnh 2 nhm (3, 4) Pht biu li bi ton:Cho mt s nguyn dng N, tm cch phn tch N thnh tng cc s nguyn dng sao cho tch S ca cc s l ln nht. 6B2: Tm cu trc d liu biu din tnh trng c th ca bi ton, tu thuc vo bi ton cn gii quyt v nhng thao tc s tin hnh trn d liu vo. Xy dng CTDL khng th tch ri vic tm kim GT. Cc tiu chun khi la chn cu trc d liu: Biu din c y cc thng tin nhp, xut. Ph hp vi cc thao tc ca GT c la chn. Ci t c trn my tnh vi NNLT ang s dng. Trc khi t chc d liu, c th phi vit mt on chng trnh nh kho st xem d liu cn lu trln ti mc no.7B2: Tm cu trc d liu Bi ton 2: Tnh S l tng bnh phng ca cc s tnhin khng ln hn N, N l s t nhin 100.S = 12 + 22 + ... + N2 Tm cu trc d liu: (NNLT s dng l C++) N c kiu s nguyn 1 byte, khng du (unsigned char). chn chnh xc CTDL ca S, chy th on chng trnh:unsigned long S = 0;// unsigned int S = 0;for(unsigned char i = 1; i 8B3: Tm gii thut Khi nim: Gii thut l mt h thng cht ch v r rng cc quy tc nhm xc nh mt dy thao tc trn cu trc d liu sao cho: Vi mt b d liu vo, sau mt s hu hn bc thc hin cc thao tc ch ra, ta t c mc tiu nh. Cc c trng ca gii thut: 1. Tnh n ngha: 1 d liu vo cho 1 kt qu ra duy nht2. Tnh dng: cho kt qu sau mt s hu hn bc. 3. Tnh ng: phi c kt qu mong mun vi mi bd liu u vo 4. Tnh ph dng: lm vic trn cc d liu khc nhau.5. Tnh kh thi: Kch thc b nh phi nh, thc hin trong thi gian cho php, d hiu v d ci t. 9B3: Tm gii thut Bi ton 3: Tm c s chung ln nht ca 2 s a, b khng ng thi bng 0. Tm gii thut: Input: 2 s nguyn t nhin a v b khng ng thi bng 0 Output: USCLN(a, b) Gii thut Euclide:B1 (Input): Nhp 2 s t nhin a v bB2: Nu b 0 th chuyn sang B3, ngc li chuyn sang B4.B3: t r = a % b; a = b; b = r; Quay tr li B2.B4 (Output): Kt lun c s chung ln nht phi tm l gitr ca a. Kt thc gii thut. 10B4: Lp trnh K thut lp trnh tt th hin k nng vit chng trnh, kh nng g ri v thao tc nhanh. Nn tin hnh lp trnh theo phng php tinh ch tng bc (Stepwise refinement): Ban u, gii thut c th hin bng ngn ng tnhin vi cc bc tng th, mi bc nu ln 1 cng vic phi thc hin. 1 cng vic n gin hoc 1 on chng trnh hc thuc th tin hnh vit m lnh ngay bng NNLT. 1 cng vic phc tp th chia ra thnh nhng cng vic nh hn v li tip tc vi nhng cng vic nh hn . Trnh vic m mm, xo i vit li nhiu ln, bin chng trnh thnh t giy nhp.11B4: Lp trnh Bi ton 4: Tm c s chung ln nht ca 2 s tnhin a, b. M t bng ngn ng t nhin nh B3: Tm gii thut on chng trnh:int a, b, r;printf(Nhap 2 so a va b: ); //B1scanf(%d%d, &a, &b);while (b != 0) //B2{r = a % b; a = b; b = r; //B3} printf(USCLN = %d, a); //B412B5: Kim th Gm 2 nhim v chnh l: 1. Chy th v tm li2. Xy dng cc b test Chy th v tm li: K nng tm li, sa li, iu chnh li chng trnh l 1 k nng quan trng ca ngi lp trnh. C ba loi li:1. Li c php: hay gp, d sa, ch cn nm vng NNLT.2. Li ci t: th hin khng ng gii thut nh, phi kt hp vi chc nng g ri sa li cho ng.3. Li gii thut: t gp, nguy him nht, c th phi iu chnh li gii thut, thm ch phi tm gii thut khc. 13B5: Kim th Xy dng cc b test: kim tra tnh ng n ca chng trnh. t trong cc file vn bn: to nhanh, mi ln chy thch cn thay tn file, khng nhp li b test t bn phm. Kinh nghim lm cc b test l:1. Mt b test nh, n gin, lm bng tay cng c c p s so snh vi kt qu chng trnh chy ra.2. Cc b test nh cha cc gi tr c bit hoc tm thng. y l nhng test d sai nht.V d: a = 0, b = 0 USCLN = 0 {l test cho kt qu sai}3. Cc b test phi a dng, trnh s lp i lp li.4. Mt vi test ln kim tra tnh chu ng ca chng trnh.14B5: Kim th Ch : Chng trnh chy qua c ht cc test khng cngha l chng trnh ng. Bi c th cha xy dng c b test lm cho chng trnh chy sai. Nn tm cch chng minh tnh ng n ca gii thut v chng trnh. Tuy nhin, iu ny thng rt kh.15B6: Ti u chng trnh Trc khi kim th nn t mc tiu vit chng trnh sao cho n gin v chy ra kt qu ng l c! Sau khi chy ng, phi sa i chng trnh chy nhanh hn, hiu qu hn. Khi ti u chng trnh, xem li nhng ch no vit cha tt th ti u li m lnh chng trnh ngn hn, chy nhanh hn. Khng nn vit ti u ti u m n , bi chng trnh c m lnh ti u thng phc tp, kh kim sot.16B6: Ti u chng trnh Vic ti u chng trnh da trn cc tiu chun sau:1. Tnh tin cy: chy ng nh d nh, m t ng mt gii thut ng, cn kim tra tnh ng n ca cc bc mi khi c th.2. Tnh uyn chuyn: d sa i, gim bt cng sc khi pht trin chng trnh.3. Tnh trong sng: d c, d hiu, ph thuc rt nhiu vo cng c lp trnh v phong cch lp trnh.4. Tnh hu hiu: chy nhanh v t tn b nh, cn phi cgii thut tt v nhng tiu xo khi lp trnh. Tiu chun ny nn dng li mc chp nhn c.17B6: Ti u chng trnh Bi ton 5: Kim tra tnh nguyn t ca s t nhin N.long kt = 1; //Gia su n la so nguyen tolong k = n - 1;for(long j = 2; j 18B6: Ti u chng trnh Ci thin thi gian chy ca chng trnh kim tra tnh nguyn t: s ln lp gim khong 1 na.long k = n / 2; Mt ci tin tip theo: s ln lp gim khong cn bc 2 ca N.long k = (long) sqrt(n); Ci tin sau gip chng trnh c th x l vi s tnhin N ln v thi gian x l nhanh hn.19Kt lun Mt chng trnh i hi rt nhiu cng on, ch 1 cng on khng hp l s lm tng chi ph vit chng trnh. Bi hc kinh nghim: ng bao gi vit chng trnh khi cha suy xt k v gii thut v nhng d liu cn thao tc. Ch cn mc 1 trong 2 li (sai v GT hoc GT khng th trin khai c trn 1 CTDL khng ph hp) th nguy c sp ton b chng trnh l hon ton cth, cng c cha cng b ri v hu nh chc chn lphi lm li t u.201.2. Vai tr ca CTDL v GT 1.2.1. Mi quan h gia CTDL v GT1.2.2. Cc tiu chun nh gi CTDL1.2.3. Cc tiu chun nh gi GT211.2.1. Mi quan h gia CTDL v GT Trong cc bc c bn khi gii quyt 1 bi ton tin hc: B1: Xc nh bi ton: c hiu bi ton thc t B2: Tm cu trc d liu: biu din cc i tng d liu ca bi ton bng cc cu trc thch hp (kiu d liu ca NNLT). B3: Tm gii thut: tm ra hng gii quyt bi ton, lcc GT xc nh trnh t cc thao tc my tnh phi thi hnh cho ra kt qu mong mun. Ni dung chnh ca mn hc l B2 v B3. B4: Lp trnh, B5: Kim th, B6: Ti u chng trnh:dnh cho cc lp trnh vin sau khi hon thnh phn m t bi ton thc t v tm ra hng gii quyt. Phn bi tp ng dng v bi tp ln ca mn hc.22Mi quan h gia CTDL v GT Sai lm thng gp: ch ch trng n GT m qun mt tm quan trng ca vic t chc CTDL ca bi ton. xc nh c GT ph hp cn phi bit n tc ng n loi CTDL no. V d: Cho 1 dy kho tng dn. Nu t chc d liu bng danh sch lin kt th phi dng GT tm kim tun t. Nhng nu t chc d liu bng mng 1 chiu th cth dng GT tm kim nh phn c tc nhanh hn. Khi chn la CTDL cng cn phi hiu r nhng thao tc (GT) no s tc ng n n. V d: Vi bi ton trn, nu tm kim c thc hin nhiu ln th nn t chc d liu kiu mng 1 chiu.23Mi quan h gia CTDL v GT Vi CTDL chn, s c nhng GT tng ng, phhp. Khi CTDL thay i, GT cng phi thay i theo trnh vic x l khng ph hp. CTDL tt s gip GT x l trn c th pht huy tc dng tt hn, va p ng nhanh va tit kim ti nguyn, GT cng d hiu v n gin hn. Trong 1 bi ton tin hc, CTDL v GT c mi quan hcht ch vi nhau, c th hin qua cng thc: :CU TRC D LIU + GII THUT = CHNG TRNH241.2.2. Cc tiu chun nh gi CTDL Trong B2: Tm cu trc d liu nu ra 1 s tiu chun khi la chn CTDL. Tuy nhin, 1 bi ton c thc nhiu CTDL m t c n, vn c t ra llm sao chn c 1 CTDL tt. Nu la chn CTDL theo 1 cch u tin no th phi l tt nht. CTDL tt l 1 CTDL tho mn cc tiu chun sau:1. CTDL ng n: m t ng cc i tng d liu.2. CTDL n gin: d tin hnh cc thao tc x l.3. CTDL tit kim ti nguyn: s dng t b nh.251.2.3. Cc tiu chun nh gi GT Trong B3: Tm gii thut nu ra 1 s tiu chun khi la chn GT x l bi ton. Khi gii 1 bi ton tin hc c th c 1 s GT khc nhau, vn l cn phi nh gi cc GT la chn 1 GT tt. Nu la chn GT theo 1 cch u tin no th phi ltt nht. GT tt l 1 GT tho mn cc tiu chun sau:1. GT ng n: cho kt qu ng vi mi b d liu vo.2. GT n gin: d ci t, ci t nhanh.3. GT thc hin nhanh: thi gian thc hin ngn. 261.3. Cc CTDL c bn 1.3.1. Khi nim kiu d liu1.3.2. Cc kiu d liu c bn1.3.3. Cc kiu d liu c cu trc271.3.1. Khi nim kiu d liu Khi nim: Kiu d liu T c xc nh bi mt b, trong :1. V: Tp cc gi tr hp l m i tng T c th lu tr.2. O: Tp cc thao tc c th thi hnh trn i tng T.V d: Kiu d liu s nguyn int trong NNLT C c xc nh bi b vi:V = {-32768..32767} v O = {+, -, *, /, %, } Cc thuc tnh ca 1 kiu d liu:1. Tn //int2. Min gi tr // [-32768, 32767]3. Kch thc lu tr //2 byte4. Tp cc ton t //+, -, *, /, %, 281.3.2. Cc kiu d liu c bn L cc loi d liu n gin, khng c cu trc, biu din cc gi tr v hng nh: s nguyn, s thc, k t, logic,... Thng c cc NNLT cp cao xy dng sn nh 1 thnh phn ca NNLT gim nh cng vic cho ngi lp trnh. Cn gi l cc kiu d liu nh sn. Cc kiu d liu c bn bao gm: Cc kiu c th t ri rc (hay cn gi l v hng m c): s nguyn, k t, logic, lit k, on con, Cc kiu c th t khng ri rc: s du phy ng, Cc kiu d liu c bn ca cc NNLT c th khc nhau i cht.291.3.3. Cc kiu d liu c cu trc Kiu d liu c cu trc l cc kiu d liu c xy dng da trn vic t chc, lin kt cc thnh phn dliu c kiu d liu c nh ngha. Cc NNLT u ci t sn 1 s kiu d liu c cu trc c bn nh: tp hp, mng, xu k t, bn ghi, tp tin... v cho php lp trnh vin t nh ngha KDL mi. Trong mn hc ny s nghin cu v 1 s CTDL phc tp hn: danh sch tuyn tnh (ngn xp, hng i), danh sch lin kt (n, vng, kp), cy (nh phn, tng qut), th,301.4. nh gi phc tp GT 1.4.1. Phng php nh gi1.4.2. Phn tch nh gi 1 GT n gin311.4.1. Phng php nh gi Thc nghim: l phng php n gin nht nh gi hiu qu ca mt gii thut (GT). Cch nh gi: Lp trnh, kim th. Thng k thi gian thc hin ca GT (theo thi gian thc). Nhc im: GT chu s hn ch ca NNLT dng ci t. Hiu qu ca GT b nh hng bi trnh ca lp trnh vin. Vic chn c cc b d liu th c trng cho tt c tp cc d liu vo ca GT rt kh khn v tn nhiu chi ph. Cc thng s kim th ph thuc nhiu vo phn cng. Kt lun: kh c kh nng p dng trn thc t!32Phng php xp x tim cn nh gi gii thut theo hng xp x tim cn: lphng php mang tnh hnh thc, khng ph thuc vo mi trng v phn cng. S dng 1 s khi nim ton hc O, , . Kch thc d liu vo (N): l lng d liu cn c x l ca bi ton. Bi ton s nguyn t: N l ln ca s nguyn cn kim tra. Bi ton sp xp dy s: N l s lng phn t ca dy s. Hm thi gian (T(N)): xc nh bi s lnh m chng trnh cn thc hin. T(N) khng ph thuc vo phn cng!33Phng php xp x tim cn Mc ch ca phng php: nh gi, so snh cc GT trong trng hp d liu vo N kh ln v theo cch c lp vi phn cng, NNLT, chng trnh dch, V d: So snh 2 gii thut P1 v P2 vi hm thi gian thc hin tng ng l T1(N) = 100N2 v T2(N) = N3. Trng hp N < 100: thi gian thc hin ca P1 v P2 t, s khc bit gia T1 v T2 l khng ng k (T1 T2 0) Khng nh gi. Trng hp N > 100: nh gi. Kt lun: P1 hiu qu P2.34Cc trng hp ca GT Mt s trng hp nh gi GT: Tt nht: hm thi gian T(N) c gi tr nh nht. Trung bnh: hm thi gian T(N) c gi tr trung bnh. c quan tm nhiu nht, i din cho a s trng hp sdng gii thut. Vic xc nh T(N) trong trng hp trung bnh thng gp nhiu kh khn v phn tch ton hc. Xu nht: hm thi gian T(N) c gi tr ln nht. c quan tm trong cc bi ton c lin quan n ri ro, y hc, ... Hoc khi gp kh khn trong nh gi GT trng hp trung bnh.35Cc trng hp ca GT V d: Xt gii thut ca bi ton s nguyn t:kt = 1; //Gi s N l s nguyn tfor (i = 2; i < N; i++)if (N % i == 0){kt = 0; //N khng l s nguyn tbreak; //Thot khi for.} Tt nht: N l 1 s chn (vng for thc hin 1 ln). Xu nht: N l 1 s nguyn t (vng for thc hin N-2 ln). Trung bnh: N l 1 s nguyn dng bt k. Rt kh xc nh T(N) trng hp trung bnh! 36Cc k php nh gi phc tp t vn : nh gi phc tp ca 1 GT, cn c lng hm thi gian T(n) ca GT vi 1 hm g(n). g(n): l 1 hm xc nh, g(n) > 0 vi mi n. Cn c vo ln ca g(n) xc nh GT l hiu qu(nu g(n) nh) hoc khng hiu qu (nu g(n) ln). K php: phc tp ca GT (cn gi l phc tp tnh ton ca GT) c xc nh trong cc trng hp (tt nht, trung bnh, xu nht) vi cc k php: K php ln (big-theta). K php ln (big-omega). K php O ln (big-oh): c s dng trong mn hc!37K php nh gi phc tp Khi nim: T(n) = (g(n))nu tn ti cc hng s dng c1, c2 v n0 sao cho:c1.g(n) T(n) c2.g(n)vi mi n n0K hiu ny gi l k php ln (big-theta notation) Hm g(n) c gi l gii hn cht (asymptotic tight bound) ca hm T(n). 38K php nh gi phc tp Khi nim: T(n) = (g(n))nu tn ti cc hng s dng c v n0 sao cho:c.g(n) T(n) vi mi n n0K hiu ny gi l k php ln (big-omega notation) Hm g(n) c gi l gii hn di (asymptotic lower bound) ca hm T(n). 39K php nh gi phc tp O Khi nim: T(n) = O(g(n))nu tn ti cc hng s dng c v n0 sao cho:c.g(n) T(n) vi mi n n0K hiu ny gi l k php O ln (big-oh notation) Hm g(n) c gi l gii hn trn (asymptotic upper bound) ca hm T(n).Lun tm c g(n) v cn tm g(n) nh nht c th!!!40K php nh gi phc tp O V d:GT vi T(n)= (n+1)2 s c phc tp l O(n2) v c thchn c cc gi tr c = 4, n0 = 14.n2 (n+1)2 vi mi n 1Cng c th kt lun T(n) = O(n3), nhng g(n) = O(n2)l hm nh nht ta tm c! Tng qut 1: GT vi T(n)= a2.n2 + a1.n + a0 (vi a0, a1, a2 l cc hng s) c phc tp l O(n2).Gii thch??? Tng qut 2: GT vi T(n)= ak.nk + ak-1.nk-1 ++ a0(vi a0,,ak l cc hng s) c phc tp l O(nk).41K php nh gi phc tp O Kt lun: Khi nh gi phc tp GT bng k php OCh quan tm n lu tha cao nht ca n!B qua cc hng s!42 phc tp ca gii thut Khi nim: phc tp ca gii thut l hm chn trn ca hm thi gian T(N). GT c hm thi gian T(N) v phc tp gii thut lg(N) nu T(N) = O(g(N)). S phn lp gii thut: cn c vo hm g(n) ngha: Cho php so snh hiu qu ca cc GT mt cch nhanh chng theo nguyn tc GT no c phc tp phn lp thp hn th hiu qu hn. Mt s phn lp thng gp: 1, lgn, n, nlgn, n2, n3, 2n, n!, nn, Hm logarit (lgn): thng gp nht l log2n, phn bit vi k hiu ton hc ca log10n.43S phn lp gii thut Hm 1 gi l hm hng s, l trng hp l tng vGT ca cc bi ton tin hc: Vi kch thc d liu vo N bt k, GT lun dng sau 1 vi cu lnh.Bi ton n gin, trng hp c bit, Cc hm lgN, N, N2, N3, gi l cc hm loi a thc. Cc GT thuc phn lp hm a thc c thi gian thc hin kh nhanh v thng c s dng. Cc hm 2N, N!, NN, c gi l hm loi m. Cc GT thuc phn lp hm loi m c thi gian thc hin rt chm v thng phi thay th bng cc GT gn ng thuc phn lp hm loi a thc!44S phn lp gii thut 2,63*10354.294.967.296 1.024160325lgN N NlgN N2 2N N!0 1 0 1 2 11 2 2 4 4 22 4 8 16 16 243 8 24 64 256 40.3204 16 64 256 65.536 2.004.189.18445S phn lp gii thut Phn tch:GT c phc tp thuc phn lp N!, vi kch thc dliu vo N = 32, s cn khong T(N) = 2,63*1035 lnh.Gi s my tnh chy chng trnh c ci t bng GT trn c tc x l khong 2,63 t php tnh/giy (2,63 GHz trong iu kin l tng) th thi gian thc hin l:T(N) = 1026 giy 3.170.979.198.376.458.650 nm 1 nm = 365 * 24 * 60 * 60 = 31.536.000 giyThi gian thc hin chng trnh hn 3 t t nm! 461.4.2. Phn tch nh gi 1 GT Bi ton: G mn (OLP Khng chuyn 2010) i c nhim thnh ph XYZ nhn c thng tin tnh bo rng, qun khng b t n qu mn trn tuyn ng cao tc, trong s c 1 qu mn hn gi vi c ch hot ng c bit. Khi c ngi tip xc vi mt qu mn bt k trong n qu mn th qu mn hn gi sb kch hot ng h m ngc ca n v sau t giy thqu mn ny s n nu cha c tho g. Cc qu mn nh s t 1 ti n dc theo quc l v cth coi v tr ca mi qu mn l mt im trn trc stheo trc quc l. Qu mn th i c ta l xi trn trc s . 471.4.2. Phn tch nh gi 1 GT Mt chuyn gia g mn hng u ca i c nhim c c n g n qu mn. Vi kh nng ca anh ta, hu nh thi gian g mt qu mn l khng ng k. Tuy nhin chuyn gia ny cn thi gian di chuyn tqu mn ny ti qu mn khc vi chi ph l 1 giy cho 1 n v di. Thi gian chuyn gia g ht cc qu mn (bao gm c qu mn hn gi) ph thuc rt nhiu vo cch chn qu mn u tin bt u g cng nh th t cc qumn cn x l.481.4.2. Phn tch nh gi 1 GT Yu cu: Cho n, t (2n, t100), k l ch s ca qu mn hn gi v ta cc qu mn (l cc s nguyn khng m khng vt qu 100). Hy xc nh thi gian ti thiu tnh t lc bt u g qu mn u tin cho ti khi g c n qu mn m qu mn hn gi khng pht n. D liu: Dng 1: cha s 2 nguyn n v t, Dng 2: cha n s nguyn theo th t tng dn l ta mn, Dng 3: cha s nguyn k. Kt qu: thi gian g c n qu mn. V d: C n = 6 qu mn v tr (1, 2, 3, 6, 8, 25), qumn hn gi l qu mn k = 5, thi gian pht n t = 4. Thi gian ti thiu g mn an ton l 31.491.4.2. Phn tch nh gi 1 GT B1: Xc nh bi ton Vn cn gii quyt: g n qu mn m mn hn gikhng n. Gi thit: cc qu mn t trn 1 trc s, ta mn tng dn, c ch mn n, Yu cu: thi gian l nh nht c th. B2: Tm cu trc d liu n, t, k: kiu s nguyn 1 byte, khng du x: kiu mng 1 chiu ca kiu s nguyn 1 byte, khng du Bin kt qu min: kiu s nguyn 1 byte, khng du501.4.2. Phn tch nh gi 1 GT B3: Tm gii thut GT 1: tng: vt cn, duyt tt c cc phng n g mn tm ra thi gian ti thiu min. M t:min = +; //Gii thut quay lui{;if ( && (tg < min)) tg = min;}printf(%d, min); nh gi: phc tp GT 1 thuc phn lp N!.511.4.2. Phn tch nh gi 1 GT GT 2: tng: ch duyt cc phng n g mn 1 cch lin tip tm ra thi gian ti thiu min. B qua cc phng n nhy cc. M t:min = +; for (i = 1; i 521.4.2. Phn tch nh gi 1 GT GT 3: tng: thi gian ti thiu min ch c th xut hin 1 trong 4 phng n g mn sau y:- Phng n 1: nu g mn t 1 n n m mn khng n.- Phng n 2: nu g mn t n n 1 m mn khng n.- Ngc li: min l gi tr nh nht trong 2 phng n 3 v 4- + Phng n 3: g mn t k n 1, ri g t k+1 n n.- + Phng n 4: g mn t k n n, ri g t k 1 n 1. Gii thch: da trn qung ng cn di chuyn gia cc qumn.531.4.2. Phn tch nh gi 1 GT M t:min = x[n] x[1]; //Phng n 1 hoc phng n 2d1 = x[k] x1; //Khong cch t mn hn gi n mn 1d2 = x[n] x[k]; //Khong cch t mn hn gi n mn nif ((d1 > t) && (d2 > t)) //Phng n 1 v 2 lm mn nif (d1 < d2)min = min + d1; //Phng n 3elsemin = min + d2; //Phng n 4}printf(%d, min); nh gi: phc tp GT 3 thuc phn lp 1.541.4.2. Phn tch nh gi 1 GT Phn tch nh gi 1 GT thng l 1 qu trnh phc tp i hi nhiu phn tch ton hc. Mc ny ch a ra cch phn tch nh gi 1 GT n gin (sau khi din t bng ngn ng t nhin hoc lp trnh bng 1 NNLT no ) gip ngi hc hiu r hn v phng php nh gi gii thut theo hng xp x tim cn. Php ton tch cc: L cc php ton thuc GT m thi gian thc hin n khng t hn thi gian thc hin cc php ton khc. Php ton tch cc c th khng phi l duy nht. Khi nh gi phc tp ca 1 GT, phng php xp x tim cn ch quan tm n cc php ton tch cc. 55Cc bc phn tch nh giBc 1: Xc nh php ton tch cc ca GT y l nhng php ton c nh hng quyt nh n thi gian thc hin ca GT.Bc 2: Xc nh s ln thc hin ca php ton tch cc Xc nh hm thi gian T(n) theo kch thc d liu nca bi ton bng cch xc nh s ln thc hin ca php ton tch cc trong cc trng hp tt nht, trung bnh, xu nht (theo yu cu).Bc 3: Kt lun phc tp GT S dng k php O kt lun hm thi gian T(n) trong cc trng hp ca bi ton.56Phn tch nh gi 1 GT n gin Xt bi ton tnh tng S ca cc giai tha t 0 n n:S = 0! + 1! + 2! + + n! C 2 cch tnh S:1. Tnh tng s hng ri cng li:Tnh i! vi i = 1..n (0! = 1: khng cn tnh)2. Da vo s hng trc tnh s hng sau:i! = (i 1)! * i Yu cu:1. Vit cc chng trnh con m t 2 GT tnh tng.2. Phn tch nh gi phc tp 2 GT trong cc trng hp tt nht, xu nht v trung bnh.57GT tnh tng s hng ri cng li Chng trnh con m t GT bng NNLT C/C++:void Tong1(){S = 1; //Khi to S = 0!for(i = 1; i 58GT tnh tng s hng ri cng li Phn tch nh gi phc tp GT:Bc 1: Xc nh php ton tch cc ca GTp = p * j;Bc 2: Xc nh s ln thc hin ca php ton tch cc Trong cc trng hp tt nht, trung bnh v xu nht, s ln thc hin ca php ton tch cc l nh nhau. Khi i chy t 1 n n, php ton tch cc thc hin i - 1ln. Tng s ln thc hin l:Bc 3: Kt lun phc tp gii thut Trong 3 trng hp phc tp GT l: T(n) = O(n2) nnnnnini 21212)1()1(...210)1( 21==++++==59GT da vo s hng trc tnh s hng sau Chng trnh con m t GT bng NNLT C/C++:void Tong2(){S = 1; //Khi to S = 0!p = 1; //Khi to p = 0!for(i = 1; i 60GT da vo s hng tnh s hng sau Phn tch nh gi phc tp GT:Bc 1: Xc nh php ton tch cc ca GTp = p * j; S = S + p;Bc 2: Xc nh s ln thc hin ca php ton tch cc Trong cc trng hp tt nht, trung bnh v xu nht, s ln thc hin ca php ton tch cc l nh nhau. Khi i chy t 1 n n, php ton tch cc thc hin 1ln. Tng s ln thc hin l:Bc 3: Kt lun phc tp gii thut Trong 3 trng hp phc tp GT l: T(n) = O(n) nni=+++==1...1111611.5. Bi tp 1.5.1. Bi tp l thuyt1.5.2. Bi tp thc hnh621.5.1. Bi tp l thuyt1. Nu cc bc c bn khi gii mt bi ton tin hc.2. Mi quan h gia cu trc d liu v gii thut trong mt bi ton tin hc.3. Hy nu mt vi cu trc d liu ca ngn ng lp trnh hc. Cc tiu chun nh gi mt cu trc d liu.4. Cc tiu chun nh gi mt gii thut. Php ton tch cc l g?5. Cc bc phn tch nh gi phc tp gii thut theo hng xp x tim cn. ngha ca cc k php dng trong phng php.631.5.2. Bi tp thc hnh6. Vit chng trnh tnh xp x ca hm ex theo 2 cch:a) Tnh ring r tng phn t ri cng vo tng.b) Tnh phn t sau da vo phn t ng trc.!nx...!2x!1x1en2x ++++=)!2()1(...!6!4!21)(2642nxxxxxCosnn++=)!12()1(...!7!5!3)(12753+++=+nxxxxxxSinnn641.5.2. Bi tp thc hnh7. Phn tch nh gi phc tp GT ca 2 GT bi tp 6 ri so snh.8. Vit chng trnh kim tra tnh nguyn t ca s tnhin N bng cc cch hc.9. Phn tch nh gi phc tp GT ca cc GT bi 8 trong trng hp tt nht, xu nht ri so snh.10. Nu 1 tng ci tin GT bi 9. 651.5.2. Bi tp thc hnh11. Phn tch nh gi phc tp cc gii thut bng k php ch O ln trong trng hp xu nht. Cho bit ni dung thc hin ca tng GT.a) float Bai1(){Sum = 0;for(i = 1; i 661.5.2. Bi tp thc hnhb) void Bai2(){for(i = 1; i 671.5.2. Bi tp thc hnhc) void Bai3(){for(i = 1; i < n; i++){for(j = 1; j < n; j++)if (X[j] > X[j + 1]){T = X[j];X[j] = X[j + 1];X[j + 1] = T;}}}