2-tema. Algoritmler natiyjeliligin bahalaw
Joba :
1. Yadlıq nátiyje, waqıt nátiyjesi.
2. Algoritmlerdıń quramalılıq dárejesi.
3. Algoritmlerdı salıstırıw usılları
Kompyuterdin’ tezligi hám yad muǵdarın máńgi asırıw múmkin, deylik. Bul jaǵdayda algoritmlerdi úyreniw kerekpe? Bar bolıwı múmkin, lekin tek kórsetiw ushın, sheshim usılın sheklengen waqıtı bar hám ol tuwrı juwap beredi.
Kompyuterler júdá tez bolǵanda, máseleni tarqatıp alıwǵa hár qanday konkret usıl uyqas kelermidi.
Álbette, búgingi kúnde júdá nátiyjeli kompyuterler, lekin olardıń islewi kútá úlken bolıwı múmkin emes. Yad da arzan, lekin biypul bolıwı múmkin emes. Sonday etip, esap -waqıtı - sheklengen resurs, sonıń menen birge yad muǵdarı da. Siz danasınıp bul resurslarini basqarıwıńız kerek, buǵan algoritmlerden, waqıt hám yad ǵárejetlerinen nátiyjeli paydalanıw kerek.
Hár túrlı máselelerdi sheshiw ushın mólsherlengen, hár qıylı algoritmler, natiyjeliligi boyınsha sezilerli dárejede parıq etedi. Bul ayırmashılıqlar kútá úlken bolıwı múmkin eken. Mısalı, eki saralaw algoritmler, 1-sabaqta talqılaw etiledi. Birinshisin orınlaw ushın, saralawdı jaylasti’ri’w, buǵan waqıt kerek boladı, sonday bahalawda c1n2, n- bul saralaw elementlerdiń sanı, c1 bolsa bul - turaqlı, n ge baylanıslı emes. Sonday etip, bul algoritmdı waqıtı shama menen n2 proportsional.
Ekinshi algoritm ámelge asırıw ushın, saralaw birlestiriwi, waqıt talap etedi, shama menen c2 n lg n ga teń, lg n- bul log2n qısqa jazıwı, c2 bul - basqa turaqlı n ge baylanıslı emes. Ádetde turaqlı usıl qosımshalar turaqlı qosılıw usılınan kishilew, c1 < c2. Turaqlı faktorlar algoritmdı jumıs waqıtına júdá kem tásir etedi, n ge baylanıslı faktorlardan kóre, soǵan isenim payda qilaylik. Saralawdı jaylastırıw algoritmdı jumıs waqtın sonday jazayınlıq c1 n n, birlestiriw saralawın bolsa c2 n lgn.
Jaylastırıw saralawı n ge iye, birlestiriw saralawı bolsa lg n ga iye bul bolsa sezirerli dárejede kemligini kóriwimiz múmkin. Kirgiziw kólemi n jeterlishe úlken bolǵanda qosıw saralawı ádetde tezirek boladı, saralaw ob'ektler kishi kólem degi birlestiriwde, úlken n ushın áhmiyetsiz ma`nisi lgn salıstırǵanda n tolıq turaqlı ayırmashılıǵı qádiriyatlar ornın oraw, tiykarınan qosılıw jáne de sezilerli kórinetuǵın boladı, saralaw abzallıǵı zıyada. Bul turaqlı c1, c2 den neshe ret kem zárúrli emes. Saralaw elementlerin qosıp saralaw jáne de nátiyjeli boladı.
Mısal formasında eki A hám B kompyuterlerdi kórip shıǵamız. A kompyuteri tezirek, hám ol jaǵdayda jaylastırıw saralawı algoritmı isleydi, B kompyuter bolsa aste hám ol jaǵdayda saralaw algoritmı birlestiriw usılı menen isleydi. Hár eki kompyuterler bir neshe saralawdı orınlawı kerek. Kompyuter A sekundına on milliard kórsetpeler atqaradı, B kompyuter sekundına tek on million kórsetpeler atqaradı, sonday etip A kompyuteri mıń ret B kompyuterden tez. Saralaw qosılıwı joqarı dárejedegi til járdeminde bir programmist tárepinen ámelge asırılǵan.
Bul kompilyator júdá nátiyjeli emes edi, hám nátiyje 50 n lg n kórsetpelerge atqaratuǵın kod payda boldı.
On million nomerlerin tártiplestiriw ushın A kompyuterge kerek boladı :
B kompyuterge kerek boladı
Kórip turǵanıńız siyaqlı, kod menen paydalanıw, jumıs waqıtı aste kóterilgende, eń aste kompyuterde ham17 ret kem waqıt talap etedi.
Qosıw usılı jaylastırıw usılınan natiyjelilew ekenligin tómende keltirilgen keste maǵlıwmatların analizi arqalı keltiremiz.
komputerler
|
Saralanatug’I’ndigan
sanlar sani’
|
Saralawshi’ algoritm
|
Talab qilinatug’i’n waqi’t
|
A(tez isleytuǵın 1 sekundda 10 mlrd ámel atqaradı )
|
10 mlnta (shama menen 80 mb)
|
Jaylastırıw usılı (tájiriybeli programmist tárepinen jaratılǵan algoritm saralaw ushın 2n2 ámel atqarıladı )
|
|
|
