|
Dasturlarni bajarilishi va bajarilish vaqtini hisoblash. Vaqt sarfi
|
| bet | 6/12 | | Sana | 04.01.2024 | | Hajmi | 75.66 Kb. | | #130056 |
Bog'liq 1-ma’ruza. Ma’lumotlar turlari. Abstraktsiya. Ma’lumotlar abstra MARJONAXON RAYIMOVA, Abduvali slayd skenirlash, Atom rus, 03-83-сонли буйрук 506-сонли буйрук асосида, Чора тадбир ИТ парк, chek, Акбар Ўрозалиев 1890 йил Андижон шаҳрининг Қорабура маҳалласида туғилган, Реабилитация, ada, 3-4 shakl Kozimov Akbarjon, 4 adabiyotlar taxlili oxirgisi 111, 01.03.2023 й. ПП ЯДАК вариант, Ibrohimova Mohichehra, Abdullayeva Mahliyo, Soxta oyoqlilarDasturlarni bajarilishi va bajarilish vaqtini hisoblash. Vaqt sarfi.Tuzilma ustida amal bajarish algoritmini bajarilish vaqtini hisoblash ko’zda tutiladi.Buni hisoblashdamashxur katta “O” notatsiya tushunchasi ishlatiladi.
Xotira sarfi.Kirish ma’lumotlarini inobatga olmagan xolda, ishlatilayotgan algoritm uchun xotiradan talab qilinadigan qo’shimcha joy sarfi tushuniladi.Bunda xam katta “O” notatsiyasi qo‘llaniladi.
Vaqt va xotira sarfini hisoblash uchun quyidagi yondashuvlar mavjud:
Katta O notatsiya. f(x)=O(g(n)) deb belgilanadi, faqat va faqat shunday musbat c va m konstanta mavjud bo’lib, f(n)<=c*g(n) tengsizlik o’rinli bo’lsa, barcha n, n>=m holatlarda.
Masalan, ushbu funksiyani 3n+2=O(n)deb olish mumkin,chunki 3n+2<=4n, n>=2 tengsizlik o’rinli. Ushbu funksiyani 6*2n+n2=O(2n) deb olish mumkin,chunki 6*2n+n2<=7*2nifoda o‘rinli,barcha n>=4 larda. O(1) deb hisoblash vaqti o’zgarmas bo’lgan holatni belgilaymiz. O(n2) ni kvadratik, O(n3) ni kubik, O(2n) ni eksponensial deb ataladi. Agar algoritmni bajarilish vaqti O(log n) bo‘lsa, O(n) ga qaraganda tezkor algoritm deb hisoblanadi.
Omega notatsiya. f(x) = Ω(g(n)) deb belgilanadi, faqat va faqat shunday musbat c va m konstanta mavjud bo’lib, f(n)<=c*g(n) tengsizlik o’rinli bo’lsa, barcha n, n>=m holatlarda.
Masalan, 3n+2=Ω(n) deb belgilash mumkin, chunki 3n+2>=3n, n>=1 tengsizlik o’rinli. 6*2n+n2=Ω (2n) deb olish mumkin, chunki 6*2n+n2>=6*2n ifoda o‘rinli, barcha n>=1 larda.
Teta notatsiya. f(x) = θ (g(n)) deb belgilanadi, faqat va faqat shunday musbat c va m konstanta mavjud bo’lib, c*g(n)<= f(n)<=c2*g(n) tengsizlik o’rinli bo’lsa, barcha n, n>=m holatlarda.
Masalan, 3n+2= θ (n) deb belgilash mumkin, chunki 3n+2>=3n, n>=1va 3n+2<=4nbarcha n>=2 da tengsizlik o’rinli. 6*2n+n2=θ (2n) deb olish mumkin,
|
| |
