Izlew hám xeshlaw algoritmler. Izlew algoritmler: Sızıqlı algoritm, ta’rtiplengen nawbetler, binar izlew. Xesh tablica hám xesh funksiyalar. Xesh funksiyalarg’a misal. Reje

4. Izlew algorimtniń nátiyjeliligi
Izbe-iz izlewdiń nátiyjeliligi
Qálegen izlewdiń nátiyjeliligi kestedegi maǵlumatlardiń giltleri menen salıstiriw sanı – S penen bahalanıwı múmkin.Eger salıstiriwlar (salıstırw) qansha kishi bolsa, izlew algoritmi nátuyjeliligi sonsha jaqsı boladi.
Massivda izbe-iz izlewdiń nátiyjeligi tómendegishe boladi:
C =1, n, C = (n + 1)/2.
Uliwma alǵanda dizimde de nátiyjelilik joqarıdaǵıday boladı. Eger massivde de baylanısqan dizimde de izlew nátiyjeliligi birdey bolsada, maǵlumatlardi massiv hám dizim kórinisinde sáwlelendiriwdiń ózine sakes kemshilidi hám apzalıǵı bar. Izlewdiń maqseti – tómendegi processlerdi orinlawdan ibarat:
1) Tabılǵan jazıwdı oqıw.
2) Izlenilip atırǵan jazıw tabılmasa,onı kestege qoyiw.
3) Tabılǵan jazıwdı óshiriw.
Birinshi process (izlewdiń ózi) massiv ushin hám dizim ushin da birdey boladı.Ekinshi hám ushinshi processde bolsa izlew dizimi duzilmede nátiyjelirek boladı( sebebi massivde elementlerdi jılıstiriw lazım).Eger k massivde elementlerdi jılıstiriwlar sanı bolsa, ol jaǵdayda k = (n + 1)/2 boladı.

Indeksli izbe-iz izlewdiń nátiyjeliligi

Eger bolıwı múmkin bolǵan bárshe jaǵdaylar teń itimali dep alınsa, ol jaǵdayda izlew nátiyjeliligin tómendegishe esaplaw múmkin:

Belgilewlerdi kiritip alamız: m – indeks ólshemi; m = n / p; p – adım ólshemi,
Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1 (*)
Q dı p boyinsha differenciallap onı nolge teńlestiremiz:
dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p2 + 1/2 = 0
Bul jerden
p2=n ; p n опт =(*) ańlatpada r ornına ropt tı qoyip tómendegi salıstırıwlar sanin alamiz: Q = n +1
Demek, indeksli izbe-iz izlewdiń nátiyjeliligi tártibi O ( n ) boladı.

5. Izlewdi quramalastiriw usılları

Uliwma alǵanda, dizimde hár bir elementti izlew itimallılıǵın qandaydir bir mánis penen ańlatiw múmkin. Meyli, umuman olganda, jadvalda xar dizimde izlenilip atırǵan element bar. Ol jaǵdayda izlew ámelge asırılıp atırǵan bárshe dizim diskret jaǵdayǵa iye dizim sıpatında qaraw múmkin hámde onda izlenilip atırǵan elementi tabiw itimallılıǵı – bul dizim i-shi jaǵdayi itimallılıǵı p(i) alıw múmkin.

Kesteni diskret Sistema sıpatında qaraǵanımızda, ondaǵı salıstırıwlar sanı diskret tosinarlı shamalar mánislerin matematik itimalligin ańlatadı.
Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)
Ílaji barınsha p(1)³p(2) ³p(3) ³…³p(n) bolsa, maqsetke muwapiq boladı. Bul shárt salıstırıwlar sanın kemeytip, nátiyjelilikti asiradı. Sebebi,izbe-iz izlew birinshi elementten baslanǵanlıǵı ushin eń kóp múrajaat etiletuǵın elementti birinshisine qoyiw lazım.