Joba: Kirisiw Algoritmlerdi analiz qiliw

3.Algoritmlardıń quramalılıǵın analiz qılıw. Mısallar
Algoritm - bul ózgeriwshen baslanǵısh maǵlıwmatlardan kerekli nátiyjege alıp keletuǵın esaplaw procesin kem ushraytuǵın tárzde belgileytuǵın anıq retsept bolıp tabıladı [1].

Algoritmlardı islep shıǵıwda esap -kitaplardı ámelge asırıw ushın zárúr bolǵan resursların bahalay alıw júdá zárúrli, bahalaw nátiyjesi quramalılıq (miynet sarpı ) funktsiyası bolıp tabıladı. Esaplanǵan resurs kóbinese protsessor waqıtı (esaplaw quramalılıǵı ) hám yad (algoritmdıń yad quramalılıǵı ) esaplanadı. Bahalaw atqarılıw waqtın boljaw hám algoritmlardıń jumıs iskerligin salıstırıw imkaniyatın beredi.

Quram :

RAM modeli (tosınarlı kirisiw mashinası )

Esaplaw operatsiyaları. Kirisiw klassları
Asimptotik belgi
Algoritm analizine mısallar
Algoritmlardı analiz qılıw ushın matematikalıq apparat
Juwmaq formulaları
Juwmaq hám integraciya
Algoritmlardıń quramalılıǵın salıstırıwlaw. shegaralar
Logarifmler hám algoritmlardıń quramalılıǵı
Analiz nátiyjeleri. Túsindirmeler. Ádebiyat

RAM modeli (tosınarlı kirisiw mashinası )

Hár bir esaplaw apparatı ayriqsha ayrıqshalıqlarǵa iye bolıp, bul esaplaw múddetine tásir etiwi múmkin. Ádetde algoritmdı proektlestiriwde protsessor keshining kólemi yamasa operatsion sistema tárepinen ámelge asırılǵan kóp wazıypalar túri sıyaqlı tolıq maǵlıwmatlar esapqa alınbaydı. Algoritmlardı analiz qılıw tosınarlı yad (RAM) mashinası dep atalatuǵın abstrakt kompyuter modelinde ámelge asıriladı.
Model yad hám protsessordan ibarat bolıp, olar tómendegishe isleydi:
yad kletkalardan ibarat bolıp, olardıń hár biri adreske iye hám maǵlıwmatlardıń bir elementin saqlawı múmkin;
hár bir yadqa kirisiw mánzillengen yacheykaning sanınan qaramastan bir birlik waqtın aladı ;
yad muǵdarı hár qanday algoritmdı orınlaw ushın etarli;
protsessor hár qanday elementar ámeldi (tiykarǵı logikalıq hám arifmetik ámeller, yaddan oqıw, yadqa jazıw, kishi programmanı shaqırıw hám t.b. ) bir waqtıniń ózinde atqaradı ;
cikl hám funksiyalar elementar ámeller esaplanbaydı.
Bunday model haqıyqıy kompyuterden uzaq bolıwına qaramay, ol algoritmlardı analiz qılıw ushın júdá sáykes keledi. Algoritm málim bir kompyuter ushın ámelge asırılǵannan keyin, siz profillew hám tómen dárejedegi optimallashtirishni ámelge asırıwıńız múmkin, biraq bul algoritmdı optimallastırıw emes, bálki kodtı optimallastırıw boladı.
Esaplaw operatsiyaları. Kirisiw klassları
Quramalılıqtı (Tn) bahalaw usıllarınan biri orınlanǵan operatsiyalar sanın esaplaw bolıp tabıladı. Mısalı, dızbektiń minimal elementin tabıw algoritmın kórip shıǵıń.
начало; поиск минимального элемента массива array из N элементов
min := array[1]
для i от 2 до N выполнять:
если array[i] < min
min := array[i]
конец; вернуть min
Bul algoritmdı orınlawda tómendegiler ámelge asıriladı :

N — 1 cikl esaplagichiga jańa baha beriw operatsiyası i;

N - N ma`nisi menen 1 esaplaǵısh salıstırıwlaw operatsiyası ;
N — dızbek elementlerin min ma`nisi menen salıstırıwdıń 1 operatsiyası ;
1 den N ge shekem ózgeriwshige baha beriw operatsiyaları min.
Ámeliyatlardıń anıq sanı qayta islenip atırǵan maǵlıwmatlarǵa baylanıslı boladı, sol sebepli eń jaqsı, eń jaman hám ortasha jaǵdaylar haqqında sóylew logikalıq jaqtan. Usınıń menen birge, mudamı eń jaman jaǵdayǵa bólek itibar qaratıladı, sonday-aq " jaman" maǵlıwmatlar basqınshı tárepinen kózaba kiriwge jiberiliwi múmkin.
Ortasha jaǵday túsinigi maǵlıwmatlar kompleksiniń birdey múmkinshiligı bar ekenin shama etken halda algoritmdıń háreketin bahalaw ushın isletiledi. Biraq, bunday bahalaw talay quramalı :
bir gruppanıń hár qanday maǵlıwmatlar kompleksi ushın algoritm (ti) quramalılıǵı birdey bolıwı ushın dáslepki maǵlıwmatlar gruppalarǵa bólinedi;
jıynaqlardıń ulıwma sanı daǵı gruppa maǵlıwmatlar kompleksiniń úlesinen kelip shıǵıp, hár bir gruppa (pi) ushın itimallıq esaplanadı ;
jumıs boyınsha ortasha ball tómendegi formula boyınsha esaplanadı : ∑i=1 mpi⋅ti.
Asimptotik belgi
Ámeliyatlar sanın esaplaw algoritmlardıń natiyjeliligin salıstırıw imkaniyatın beredi. Biraq, soǵan uqsas nátiyjeni ápiwayılaw usılda alıw múmkin. Analiz qayta islengen maǵlıwmatlardıń etarlicha úlken muǵdarın (n→∞) kútiw menen ámelge asıriladı, sol sebepli operatsiyalardıń anıq sanı emes, bálki quramalılıq funktsiyasınıń ósiw tezligi tiykarǵı áhmiyetke iye.
Ósiw pátin analiz qılıwda ańlatpa daǵı turaqlı shártler hám kóbeyiwshiler itibarǵa alınbaydı, yaǵnıy. fx=10⋅x2+20 hám gx=x2 funktsiyaları ósiw tezligi boyınsha ekvivalent. Zárúrli bolmaǵan aǵzalar tek " tolqınlilik" ni qosadı, bul bolsa analizdi quramalılastıradı.

Algoritmlardı bahalawda tómendegi funktsiyalar klassların anıqlaytuǵın arnawlı asimptotik belgiler qollanıladı :

O (g) - funksiyalar g den aste ósedi;
Ω(g) - g den tezirek ósetuǵın funktsiyalar ;
(g) funksiyalar g menen birdey tezlikte ósedi.
=O ( ) jazıwı f funksiyanıń O (g) klasına tiyisli ekenligin ańlatadı, yaǵnıy. f funktsiyası joqarıdan argumentning jeterlishe úlken bahaları ushın g funktsiyası menen shegaralanǵan. ∃ >0, c>0:∀n> , ≤c⋅ .

g funksiyanıń f funksiya menen tómenden shegaralanǵanlıǵı tómendegishe jazıladı : = Ω ( ). Ō hám O belgilerin almastırıw múmkin: =O ( ) ⇔ = Ω ( ).

Juwmaq
Quramalılıqtı bahalaw tek ǵana algoritmlardı salıstırıw, bálki olar qansha waqıt islewin boljawdıń ájayıp usılı esaplanadı. Hesh qanday islew testleri bunday maǵlıwmattı bermeydi, sebebi. málim bir kompyuterdiń qásiyetlerine baylanıslı hám arnawlı bir maǵlıwmatlardı qayta isleydi (eń jaman jaǵday emes).

Algoritmlardı analiz qılıw minimal múmkin bolǵan quramalılıqtı anıqlawǵa múmkinshilik beredi, mısalı :
Tártipsiz dızbektegi elementti tabıw algoritmı O (n) den jaqsılaw shegaralanǵan joqarı quramalılıqqa ıyelewi múmkin emes. Óytkeni sonda, dızbekte element joq ekenligin (eń jaman jaǵdayda ) onıń barlıq elementlerin kórip chiqmasdan turıp anıqlaw múmkin emes;
O (n⋅logn) den jaqsılaw isleytuǵın qálegen dızbekti tártiplew múmkin emesligin rásmiy tastıyıqlaw múmkin [5].
Kóbinese intervyularda olardan ılajı bolǵanınsha jaqsılaw esaplanǵan algoritmdı islep shıǵıw soraladı. wazıypalardıń ózi birpara standart algoritmǵa qısqartiriladi. Asimptotik analiz menen tanıs bolmaǵan adam kod jazıwdı baslaydı, biraq talap etiletuǵın zat bunday algoritmdıń bar ekenligin múmkin emesligin aqlaw bolıp tabıladı.

Paydalanilg’an a’debiyatlar

1. 
   Васильев В. С. Алгоритм. Свойства алгоритма [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/578. Дата обращения: 06.01.2014.
   
2. 
   Васильев В. С. Блок-схемы алгоритмов сортировки пузырьком, выбором и вставками [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/1462. Дата обращения: 06.01.2014.
   
3. 
   Дж. Макконелл Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. М: Техносфера, 2009. -416с.
   
4. 
   Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер ; пер. с англ. — М. : БИНОМ. Лаборатория знаний, 2006. — 406 с.
   
5. 
   Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил.