i i “Klavzar-casovna-zahtevnost” — 2010/5/27 — 10:25 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 14 (1986/1987) Številka 2 Strani 125–128 Sandi Klavžar: ČASOVNA ZAHTEVNOST ALGORITMOV Ključne besede: matematika, računalništvo, algoritem, časovna zah- tevnost. Elektronska verzija: http://www.presek.si/14/826-Klavzar.pdf c© 1986 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno. CASOVNA ZAHTEVNOST ALGORITMOV Gotovo so med vami lastniki računa lnika SPECTRUM 16 K. Prepričan sem, da so se že večkrat jezili , ker niso mogli naložiti programov, ki so sicer pisani za povsem enak računalnik SPECTRUM 48 K, le da ima slednji na razpolago večji pomn il nik. Zadnjič sem videl sprogramiran šah za mikroračunalnik , ki ima, kot seto seveda spodobi, več t ežavnostn ih stopenj . Na nižjih stopn jah ga je kaj lahko premagati, če niste prehud začetnik. Problem pa nastane, če bi hote li ugotovi- ti, kako igra na najzahtevnejši stopnj i. Približni čas, ki si ga računalnik vzame za eno potezo, je namreč nič več in n ič manj kot 24 ur. Rad bi ga poznal , ki je z računalnikom odigral ta šah na najzahtevnejši stopnji! V prvem pr imeru smo naleteli na težave s prostorom in v drugem pr imeru na težave s časom. Zato si oglejmo , kako bi prostor in čas, ki ju potrebuje raču ­ nalnik, natančnejedefinirali. Ker nas bolj zanima časovna zahtevnost algoritma, bomo pustili prostor- sko zahtevnost ob strani. Algoritem lahko definiramo povsem strogo, vendar naj nam zadošča že intuitivna slika. Recimo , da rešujemo neki problem. Algo- ritem je spisek natančno določenih navodil , ki nas vkončnem času po strogo začrtani poti pripeljejo do rešit ve problema. Problem lahko rešimo na več na- činov (z različnimi algoritmi). A lgoritem bo tem boljši, čim manj prostora in čim manj časa bo porabil. Vsak problem ima tudi svojo velikost. Velikost pro - blema je mera za obsežnost vhodnih podatkov. Če na pr imer urejamo neko za- poredje, je velikost problema število elementov zaporedja, ki ga želimo urediti. Definicija 1. Časovna zahtevnost algoritma je čas, ki ga potrebuje algoritem za rešitev problema pri dani velikosti problema. Čas je funkcija velikosti problema. Ker različni računalniki različno hitro računajo, je smiselno, da za enoto časa vzamemo osnovno računsko operacijo (seštevanje, odštevanje, množenje, deljenje). Ravno tako za enoto štejemo primerjanje vrednost i dveh spremenljivk. Če je časovna zahtevnost 3n 4 - 5n , algoritem opravi 3n 4 - 5n osnovnih računskih operacij in primerjan], Podobno definiramo prostorsko zahtevnost algoritma. Zanimala nas bo le hitrost rast i zahtevnosti algoritma in ne točna vrednost, zato definirajmo: Definicija 2. Funkcija gIn) je O(f(n)), če obstaja konstanta C >0, tako da je: gIn) ~ C.f(n) , za vse dovolj velike n. Definicija potrebuje nekaj pojasnil. Da gIn) ~ C.f(n) velja za vse dovolj velike n, pomeni, da velja za vsa naravna števila, ki so večja od nekega naravne- 125 ga števila no. Izjavo gIn) = O(f(n)) preberemo takole: funkcija gIn) je "veliki o od" fIn) . Časovno zahtevnost algoritma (in tudi prostorsko) navadno opišemo s pomočjo velikega o. Primer 1. Velikokrat imamo opraviti z zahtevnostjo, ki se izraža s polinomom v velikosti problema . Polinom gIn) stopnje k je funkcija oblike kjer so koeficienti aj poljubna realna števila in je an =1= O. Recimo, da je gIn) = = 2n 4 + n 3 - n2 - 23n + 10. Tedaj je zahtevnost algoritma O(n4 ) . Če namreč za konstanto C vzamemo C = 3, potem je pogoj 2n 4+n3-n2-23n+10 ~ 3n 4 izpolnjen kar za vsa naravna števila in lahko izberemo no =O. Nasploh velja, da zahtevnost polinoma dobimo tako, da vzamemo vodilno potenco polinoma. Tako je 5n 3 + 100n2 + 99n = O(n 3 ). Kako velik no moramo vzeti, če izbere- mo C = 6? (no = 100). Seveda bi bil no manjši, če bi izbrali večjo konstanto C. Vprašajmo se, kakšna je časovna zahtevnost algoritma za igranje šaha. V načelu je algoritem tak, da pregleda vse kombinacije in se nato odloči za naj- boljšo. No, vseh možnih kombinacij do konca partije prav gotovo ne bo pre- gledal. Za koliko potez vnaprej naj torej gleda vsemožnosti? Če gleda samo za eno potezo, tedaj niti ni tako veliko možnosti. Seveda bo igral temu primerno slabo. Če se odloči za dve, mora upoštevati vse možne nasprotnikove odgovore na prvo potezo ... Gotovo slutite, da število kombinacij z vsako naslednjo po- tezo strahovito hitro raste. Seveda bo igral tem bolje, čim več potez vnaprej bo gledal. Odtod izvira velika poraba časa za igranje na zahtevnejših stopnjah. Ustvarjalci programov za igranje šaha se zato trudijo, da bi z globljim pozna- vanjem šaha pregledovali samo nekatere kombinacije in se med temi odločili za pravo potezo. V ocenjevanju zahtevnosti imajo poseben pomen eksponentne funkcije. Funcija fIn) je eksponentna, če je oblike fIn) = an, kjer je a neko pozitivno število. Primer eksponentnih funkcij sta fIn) == 2n in fIn) = en. Naloga. Pokaži, da funkcija fIn) = 2n ni O(nk ) za noben k. Glavna značilnost eksponentnih funkcij je, da strahovito hitro naraščajo. Po- znamo tudi funkcije, ki naraščajo šehitreje kot eksponentne, na primer fIn) = 2 2n pa tudi take, ki naraščajo počasneje kot eksponentne, pa vendar hitreje kot katerakoli potenca (na primer fIn) = n Iogn). Kakršnokoli funkcijo izmed omenjenih že srečamo, senam ne piše dobro. 126 Naloga. Recimo, da je velikost problema n. Imamo tri algoritme: prvi je zahte- vnosti n, drugi n3 in tretji 3" . Predpostavimo, da ručunalnik za eno operacijo potrebuje mikrosekundo (10-6 s). Kako velika je lahko naloga v vsakem od primerov, če imamo na razpolago uro računalniškega časa (3.6.109,1532, 20)? Algoritem je eksponenten, če je zahtevnosti O(f(n)), kjer je f(n) eksponentna funkcija. Podobno je algoritem polinomski, če je zahtevnosti O(f(n)l. kjer je f(n) polinom. Problem igranja šaha je po svoji naravi časovno zelo zahteven, saj je njegova zahtevnost vsaj eksponentna, če ne celo več. Če za dani problem ne znamo poiskati boljšega kot eksponentni algoritem, potem lahko obupamo ali pa malo pogoljufamo pri reševanju problema na različne načine. Pri šahu po- goljufamo tako, da ne gledamo preveč potez vnaprej in s tem naredimo pro- blem majhen. Naloga. Morda kdo misli, da bodo hitrejši računalniki rešili počasne algoritme. Vendar temu ni tako. Recimo, da imamo na razpolago tisočkrat hitrejši raču­ nalnik kot v prejšnji nalogi, torej osnovno operacijo opravi v nanosekundi (10-9 s). Za iste zahtevnosti se zopet vprašajmo po največji obsežnosti, ki jo za vsakega med njimi lahko opravimo veni uri (3.6.1012 , 15327,26). Opazimo, da smo pri eksponentnem algoritmu zelo malo pridobili. Za konec si oglejmo še nekaj primerov. Primer 2. Iskanje največjega elementa zaporedja. Recimo, da imamo neko poljubno zaporedje n števil, v katerem moramo poiskati največji element . Prav gotovo moramo pogledati vsa števila, saj bi lahko bilo največje število ravno tisto, ki ga nismo pogledali. Narediti moramo torej vsaj n osnovnih operacij. Sestavi algoritem, ki bo poiskal največji element zaporedja v času O(n). Primer 3. Urejanje zaporedja. V praksi se velikokrat srečamo s problemom urejanja zaporedja. Zanj je izdelana že zelo obsežna teorija. Morda najpreprostejši algoritem bi bil nasle- dnji: poiščemo največji element in gadamo na prvo mesto, nato med preostali- mi poiščemo največjega in ga damo na drugo mesto, ... Poizkusi dokazati, da je časovna zahtevnost tega algoritma O(n 2 ) . Toliko časa algoritem potrebuje tu- di v primeru, ko so vhodni podatki že urejeni. Radovednejšim naj povemo, da je časovna zahtevnost najboljših algoritmov za urejanje O(n.logn). Primer 4. Delitev množice. Imejmo končno množico A z elementi iz množice naravnih števil. Vprašaj- mo se, ali lahko to množico razdelimo na dve podmnožici Al in A 2 tako, da je vsota elementov v podmnožicah enaka. Če je A = { 13, 4, 10, 11,8} , sta mno- žici Al = { 13, lO} in A z = {,4, 11, 8l rešitev problema delitve množiceA. Problem je videti preprost, tako da ga verjetno ni težko rešiti. Vendar nasprvi 127 vtk ne sme zwen:i. Doaedaj nam& ik niMe nl ndel polimdcega a l g ~ r h a re problem delitve rnnoBce (rmj opzurimo, da je v tern primem wlikost n a b ge d o h a ~epbe pmhtkov tn rn redm neJvei5je dam hilo) . -lo &: Cle bi komu to uopslo, bi s tern &il tudi wdiko b i S o dru$ih pmmbnih proble- m (nekaj tisoel), za k a t m ~ tudi L ne poznamo polEnomskeg~ algoritma