Bob. Algoritmlar haqida dastlabki tushunchalar

Saralash

algoritmi

Sarflanadigan

vaqt

Izoh

Joyiashtirish

usuli

Cm2  bu 

n2  ga 

proporsional

Ci-n  ga  bog‘liq  bo‘lmagan 

doimiylik

n-saralanadigan 

elementlar 

soni

Q o‘shish

usuli

C2nlgn

lgn=log

2

n,

Сг-п  ga  bog‘liq  bo‘lmagan 

doimiylik

Q o‘shish  usuli  joyiashtirish  usulidan  samaraliroq  ekanligini 

quyida keltirilgan jadval  m a’lumotlarini tahlili  orqali  keltiramiz.

1  Thomas  H.  Cormen  va  b.  Intruduclion  to  algorithms.  Massachusetts  Institute  o f  Technology.

London 2009.(5-lOpp)

6

---

K o m p u -

te rla r

S a ra la n a -

d igan

so n la r

son i

S a ra lo v ch i

a lg o ritm

T alab   q ilin a d ig a n   vaq t

A (tez

Joylashtirish

ish lo v ch i

usuli  (tajri-

2 * (107)2 

ar

lse k u n d d a

bali  dastur-

JQ30 

buyruq Js

lO m lrd

chi  tom oni­

am al

dan  yaratil-

=

20000 sec

b aja rad i)

gan  algo­

(5,5 soatdan ко 'proq)

S '

ritm  sara­

£

о

lash  uchun

oo

с

2n2 amal

C

5J

x>

bajariladi)

B (sek in

1-1

СГ

сб

Q o‘shish

ish lo v c h -

B"

usuli

50» 107  I g l 07

-----------— -----«

j

  1163 

sekund

lse k u n d d a

с

(o‘rta  dara-

107

10  m ln

£

jali  dastur-

am al

о

chi  tomoni­

(20minrftm>ami)

b aja ra d i)

dan  yaratil-

gan  algo­

ritm  sara­

lash  uchun

50nlgnamal

bajariladi))

Umurnan  olganda  algoritm  -  bu  qo‘yilgan  masalaning  yechi- 

miga  olib  keladigan,  ma'lum  qoidaga  binoan  bajariladigan 

amallarning  chekli  qadamlar  ketma-ketligidir.  Boshqacha  qilib 

aytganda.  algoritm  boshlang‘ish  ma'lurnotlardan  natijagasha  olib 

keluvshi jarayonning aniq  yozilishidir.

Algoritm  tushunshasining  turli  ta ’riflari  bir  qator  talablarga 

javob berishi  kerak:

-  algoritm  chekli  sondagi  elementar  bajariluvshi  ko‘rsatma- 

lardan  iborat bo‘lishi  kerak;

-  algoritm chekli  sondagi  qadamiardan  iborat boMishi  kerak;

---

-  algoritm  barcha  boshlang'ich  berilganlar  uchun  umumiy 

bo'lishi  kerak;

-  algoritm  to 'g 'ri  yechimga olib  kelishi  kerak.

Har  qanday  algoritm  ma'lutn  ko‘rsatmalarga  binoan  bajariladi 

va  bu  k o ‘rsatmalarga  buyruq  deyiladi.  Yuqoridagi  fikrga  k o ‘ra 

algoritm asosan masalani  yechimini  topish  uchun tuziladi.

Bitta  masalani  yechishning  bir  necha  algoritmi  mavjud  bo'lishi 

mumkin.  Ular  orasida  eng  samaralisini,  bajarilishi  uchun  eng  kam 

amallar,  mashina  vaqti,  xotira  va  h.k.ni  talab  qiluvchi  algoritmni 

tanlash  lozim.  Samarali  algoritmlar  mavjud  bo  iish  shartlari  va 

ularni  qurish  (ishlab  chiqich)ni  o'rganish  algoritmlar  nazariyasi 

asosini  tashkii  etadi.

Algoritm  kibernetika  va  matematikaning  asosiy  tushuncha- 

laridan  biri  bo'lib,  bu  atama  o 'rta  asrlarda  yashab  ijod  etgan  buyuk 

o 'zb ek  matematigi  Al-Xorazmiy  nomidan  kelib  chiqqan.  U  IX 

asm ing  825  yilidayoq  o'zi  kashf  etgan  o'nli  sanoq  tizimida  to ‘rt 

arifmetika  amallarini  bajarish  qoidalarini  bergan.  Arifmetika 

amallarini  bajarish  jarayoni  esa  al-xorazm  deb  atalgan.  Bu  atama 

1747  yildan  boshlab algorismus,  1950  yilga  kelib  algorifm  deb  ham 

ataldi.  Fanda  "Yevklid  algoritmi",  "G'iyosiddin  Koshiy  algoritmi", 

"Laure  algoritmi",  "Markov  algoritmi"  deb  ataluvchi  algoritmlar 

m a ’lum  algoritm  tushunchasi  tobora  kengayib  borib,  kibernetika- 

ning  nazariy  va  mantiqiy  asosi  hisoblangan  algoritmlar  nazariyasi 

paydo  bo'lgan.  Kompyuterlar paydo  bo'lishi  bilan  algoritm  atamasi 

hozirgi  m a'nosi  bilan  axborot  texnologiyalari  sohasida  eng  asosiy 

atamalardan  biri  bo'lib  qoldi.  Odatda  algoritmlar  u  yoki  bu 

hisoblashga  doir  masalaiarni