Joba: Kirisiw Algoritm waqit ha’m ko’lemli quramalig’in bahalaw

Tema:Algoritmlardi waqit ha’m ko’lemli bahalawda tegis ha’m logorifmlik salistirma miyzanlari
Joba:
Kirisiw
1. Algoritm waqit ha’m ko’lemli quramalig’in bahalaw
2. Algoritmdi quramalilig’in bahalaw
3. Algoritm ko’lemi
Juwmaq
Paydalanilg’an a’debiyatlar

Kirisiw
Ámeldegi algoritmlardıń ko'pshiligi yad hám tezlik ortasında tańlawdı usınıs etedi. Másele tez islewi hám úlken yad iyelewi yamasa aste islewi hám kishi yad kólemin iyelewi múmkin. Bul jaǵdayda eń ádetiy mısallardan biri eń qısqa aralıqtı tabıw máselesi bóle aladı. Bunda siz óz-ara baylanıslı bolǵan qala arasındaǵı qálegen eki noqat arasındaǵı eń qısqa aralıqtı tabıwıńız kerek boladı. Bunda biz barlıq noqatlar arasındaǵı qısqa aralıqlardı anıqlap olardı keste formasında saqlap qoyıwımız múmkin. hám biz eń qısqa aralıqtı anıqlawımızǵa tuwrı kelip jaysha kesteden maǵlıwmattı alıp qoyıwımız múmkin boladı.

1.Algoritm waqit ha’m ko’lemli quramalig’in bahalaw
Ámeldegi algoritmlardıń ko'pshiligi yad hám tezlik ortasında tańlawdı usınıs etedi. Másele tez islewi hám úlken yad iyelewi yamasa aste islewi hám kishi yad kólemin iyelewi múmkin. Bul jaǵdayda eń ádetiy mısallardan biri eń qısqa aralıqtı tabıw máselesi bóle aladı. Bunda siz óz-ara baylanıslı bolǵan qala arasındaǵı qálegen eki noqat arasındaǵı eń qısqa aralıqtı tabıwıńız kerek boladı. Bunda biz barlıq noqatlar arasındaǵı qısqa aralıqlardı anıqlap olardı keste formasında saqlap qoyıwımız múmkin. hám biz eń qısqa aralıqtı anıqlawımızǵa tuwrı kelip jaysha kesteden maǵlıwmattı alıp qoyıwımız múmkin boladı.
Nátiyjeni sol zamatı alıwımız múmkin, biraq bul kútá úlken kólem talap etedi. Mısalı qandayda bir úlken kartada 10 mińlaǵan noqatlar bolıwı múmkin hám biziń kesteimiz onıń ushın 10 milliarddan artıq maǵlıwmattı saqlawına tuwrı keledi jáne bul shama menen 10 GB ga jaqın yadtı bánt etiwi múmkin. Bul jaǵdaydan kólem-waqıt quramalılıǵı kelip shıǵadı. Sonda algoritm waqıt boyınsha islew tezligi yamasa kólem boyınsha islew tezligi menen bahalanadı.
Biz tiykarǵı itibardı waqıt boyınsha quramalılıqqa qaratamız lekin sol menen birge paydalaniletuǵın yad kólemin da anıq belgilewimizga tuwrı keledi.
Izbe-izlikti bahalaw.
Biz algoritmlardı óz-ara bahalawımızda olarǵa kiretuǵın maǵlıwmattı da itibarǵa alıwımızǵa tuwrı keledi. Sebebi áyne bir saralaw algoritmı ushın 1000 ta kiretuǵın elementti saralaw 1 s, 100 000 element ushın bolsa 4-5 sekund ketetuǵın bolsa, basqa bir algoritm ushın bolsa bar-yo'g'i 2 s ketiwi múmkin. Bunday sharayatta qaysı algoritm jaqsı ekenin búydew qıyınshılıqlı bolıp tabıladı. Ulıwma jaǵdayda bolsa algoritmdı quramalılıǵın áyne bir shama menen bahalaw múmkin boladı. Bunı tómendegishe túsiniw múmkin: eger algoritmga kiretuǵın N maǵlıwmatlar asqanında algoritmdıń atqarılıw waqıtı f (N) funksiya menen birdeyde ortsa algoritm O (f (N)) quramalılıqqa iye dep ataladı.
Keling, jaqsısı A[NxN] matritsaning hár bir qatarındaǵı maksimal

elementti tabıwdı kórip shıǵamız :

Bul algoritmda i ózgeriwshi 0 den N-1 ge shekem ózgerip kelip atır
hám de onıń hár bir ózgeriwinde j ózgeriwshi de sol aralıqta ózgerip atır.
Sonday eken bunda jámi N*N ret tákirarlanıw júz bolıp atır. Bunnan bolsa f (N) = N*N ga teń boladı hám algoritmdıń quramalılıǵı O (N*N) ekenligin anıqlawımız múmkin.