Algoritm murakkabligini baholash. Xotira yoki vaqt

Xulosa

Xulosa o’rnida aytadigan bo’lsak, algoritmlar asosan quyidagicha ko’rinishdagi murakkabliklarda bo’ladi va barcha algoritmlarni baholashimiz uchun mana shu murakkabliklar yetarli bo’ladi:

1. 
   C yoki O(1) - algoritm o’zgarmas vaqtda bajariladi.
   
2. 
   O(log(log(N)))
   
3. 
   O(log(N))
   

4. O(N^C) 0

5. 
   O(N)
   
6. 
   O(N*log(N))
   

7. O(N^C) C > 1
8. O(C^N) C > 1 9. O(N!)
Agar biz ushbu murakkablikni aniqlaydigan bo’lsak:
O(log(N) + N!) = O(N!). Bunda f(N) = N! funksiya f(N) = log(N) funksiyadan ko’ra tezroq o’suvchi. Shuning uchun algoritmning murakkabligini O(N!) deb olishimiz yetarli bo’ladi. Quyida murakkabliklarning turli kiruvchi ma’lumotlardagi bajarilish vaqti keltirilgan:

Xulosa
Bir xil muammoni hal qilishning to'rtta algoritmini ko'rib chiqing, ular qiyinchiliklarga duch keladi va mos ravishda. Aytaylik, ushbu algoritmlarning ikkinchisi parametr qiymati bo'lgan ba'zi bir kompyuterda bajarilishi uchun bir daqiqalik vaqtni talab qiladi. Keyin ushbu to'rtta algoritmni bir xil kompyuterda parametrning turli qiymatlarida bajarilish vaqti taxminan 10,300,000 yil bilan bir xil bo'ladi

Dasturchilar o'z dasturlarini sinashni boshlashganda, ularga bog'liq bo'lgan parametrlarning qiymati odatda kichik bo'ladi. Shuning uchun, dasturni yozishda samarasiz algoritm ishlatilgan bo'lsa ham, u e'tiborga olinmasligi mumkin. Ammo, agar siz bunday dasturni real sharoitlarda qo'llashga harakat qilsangiz, unda uning amaliy foydasizligi darhol namoyon bo'ladi.
Kompyuterlar tezligining oshishi bilan u yoki bu algoritmning ishlashi maqbul vaqt ichida bajariladigan parametrlarning qiymati ham oshadi. Shunday qilib, miqdorning o'rtacha qiymati oshadi va shuning uchun tez va sekin algoritmlarning bajarilish vaqtining nisbati oshadi. Kompyuter tezroq ishlaydi, yomon algoritmdan foydalanganda nisbiy yo'qotish katta bo'ladi!

Adabiyotlar:
1. Abramov S.A. i dr. Zadachi po programmirovaniyu.-M.:Nauka, 1988.-224
str.
2. Гуломов С.С. ва бошқалар. Ахборот тизимлари ва технологиялари. Тошкент,
2000
3. Axo A., Xopkroft Dj. Postroyeniye i analiz vychislitelnyx algoritmov.
- M: Mir, 1979 g., 535 s.
4. Virt N.. Algoritmy i struktury dannyx. – Dossa, Xamarayan, 1997.
5. Knut D. Iskusstvo programmirovaniya dlya EVM. Osnovnye algoritmy.-M:
Mir, 2000 g.
6. Kormen T., Leyzerson Ch., Rivest R. Algoritmy: postroyeniye i analiz. M.:
MSNMO, 2001.- 960 s.
7. Lebedev V.I. Vvedeniye v sistemy programmirovaniya. M: Statistika,
1975.
8. Polyakov D.B., Kruglov I.Yu. Programmirovaniye v srede Турбо Пасcал:
Sprav.-metod. posobiye.- M.: Izd-vo MAI, 1992.-576 s.