3-Laboratoriyalıq jumıs. Tyuring mashinasın jasaw. Jumıstıń maqseti

Algoritmdi dúziw.

1. 
   Baslaniwi
   
2. 
   M di n ge bólemiz qaldiq r ge teń bolsin.
   
3. 
   Eger r=0 onda n-nátiyje; 5ke otiń;
   
4. 
   M:=n; n:=r; 2 ge ótiń;
   
5. 
   Tamam.
   

Algoritm analizi:
Usi algoritmdi analizlep kóreyik.
M=119, n=544 dep qabil eteyik. Ekinshi adimnan baslaymiz. Algoritmǵa muwapiq bóliw nátiyjesin 0 ge teń dep esaplaymiz hám r ǵa 119 di támiyinleymiz, keyin 3-adimǵa ótemiz. R nólge teń bolmaǵanliǵI sebepli hesh nárse qilmaymiz hám 4-adimǵa ótemiz. Bul jerde m ǵa 544 ti n ǵa 119 di táminleymiz. Uliwma aniq boldi mAlgoritmdi optimallastiriw:
Algoritmdi optimallastiriw ushın oǵan tómendegi adimdi qosamiz:
Eger mEndi 2-adimǵa kelsek 544/119=4,68/119. R ǵa 68 di qabil etemiz. 3-adim islemeydi. 4-adimda n=68, m=544, r=68. Keyingi sikllarda (r=51, m=68, n=51), keyin (r=17, m=51, n=17) hám 51/17, yaǵniy r=0.
Solay etip, algoritm sikli 3-adimda tamamlanadi hám 544 hám 119 lardiń uliwma bóliwshisi 17 ge teń boldi.
Bul algoritm uliwma bóliwshini tabiw ushın jalǵiz emes. Bunday algoritmdi tabiw ushın Dj.Steynniń binary algoritmi yakiy V xorristiń algoritminan paydalaniladi.
Algoritmdi ámelge asiriw:
Usi algoritmdi kompyuterda ámelge asiriw ushın tómendegi Paskal dasturin keltiriw múmkin.
Asimptotik belgiler.
1.O - úlken O
2
3.⍬ - Teta
Úlken O
O(g)-funkciyalar toplami esaplanip g-dan tez óspeydi. g(n) – O(g) algoritminiń eń jaman orınlaw jaǵdayin kórsetedi.

Ulken Ω
Ω- funkciyalar toplami esaplanip, algoritmnin; orınlaniw waqtiniń tómengi shegarasin aniqlaydi.
g(n)- Ω algoritmniń eń jaqsi orınlaw jaǵdayin kórsetedi.

Úlken ⍬
⍬-funkciyalar toplami esaplanip, algoritmniń orınlaniw waqtiniń tómengi hám joqarǵI shegarasin aniqlaydi.
g(n)-⍬ algoritmniń ortasha orınlaw waqtin kórsetedi.