1-amaliy mashg’ulot. Ma’lumotlar tuzilmalari ustida bajariladigan amallar. Ma’lumotlarning strukturlashganligi va dasturlash texnologiyasi algoritmlarning murakkabligi



Download 45,27 Kb.
bet1/6
Sana07.04.2022
Hajmi45,27 Kb.
#534992
  1   2   3   4   5   6
Bog'liq
1-amaliyot


1-amaliy mashg’ulot. MA’LUMOTLAR TUZILMALARI USTIDA BAJARILADIGAN AMALLAR. MA’LUMOTLARNING STRUKTURLASHGANLIGI VA DASTURLASH TEXNOLOGIYASI
Algoritmlarning murakkabligi. Hisoblash muammolari cheklangan xotira resurslaridan foydalangan holda oqilona vaqt ichida yechilishi kerak. Bu algoritmning vaqt va fazoviy murakkabligi tushunchasiga olib keladi. Qoida tariqasida, algoritm turli vaqtlarni bajarishi mumkin boʻlgan turli xil amallarni oʻz ichiga oladi.
Algoritmlarni baholash uchun koʻpgina mezonlar mavjud. Odatda kirituvchi berilganlarni koʻpayishida masalani yechish uchun kerak boʻladigan vaqt va xotira hajmlarini oʻsish tartibini aniqlash muammosi qoʻyiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini aniqlovchi qandaydir sonni bogʻlash zarur. Bunday son masalaning kattaligi deb qabul qilinadi. Masalan, ikkita matritsani koʻpaytirish masalasining oʻlchami boʻlib, matritsalar kattaligig xizmat qilishi mumkin. Graflar haqidagi masalada oʻlcham sifatida graf uchlarining soni boʻlishi mumkin.
Algoritm sarflanayotgan vaqt masalaning oʻlchami funksiyasi sifatida algoritmni vaqt boʻyicha qiyinligi deb nomlanadi. Bunday funksiyaga masalaning kattaligi oshganda limit ostidagi oʻzgarish asimptotik qiyinlik deb aytiladi.
Murakkablikni baholash. Algoritmlarning murakkabligi odatda bajarilish vaqti yoki ishlatilgan xotira boʻyicha baholanadi. Ikkala holatda ham, murakkablik kiritilgan ma’lumotlarning hajmiga bogʻliq: 100 ta elementdan iborat massivi xuddi shunga oʻxshash 1000 ta elementdan iborat massivga qaraganda tezroq qayta ishlanadi. Shu bilan birga, aniq vaqt bilan bir necha kishi qiziqadi: bu protsessorga bogʻliq, ma’lumotlar turi, dasturlash tili va boshqa koʻplab parametrlarga ham bogʻliq. Faqatgina asimptotik murakkablik muhim, ya’ni kirish ma’lumotlarining kattaligi cheksizlikka intilayotgandagi murakkablik.
Masalan, ba’zi bir algoritmga kirish ma’lumotlarining n ta elementlarini qayta ishlash uchun 4n3 + 7n ta shartli amallarni bajarish kerak. n ning ortishi bilan ishning umumiy davomiyligi n ning kubi uni 4 ga koʻpaytirgandan yoki 7n ni qoʻshgandan koʻra koʻproq ta’sir qiladi. Ushbu algoritmning vaqt murakkabligi O(n3), ya’ni u kubik bilan kiritilgan ma’lumotlarning hajmiga bogʻliq boʻladi.
Bosh harf O dan foydalanish matematikadan kelib chiqadi, bu yerda ushbu belgi funksiyalarning asimptotik harakatlarini taqqoslash uchun ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki egallagan xotira miqdori), kiritilgan ma’lumotlarning hajmiga qarab, f(n) ga koʻpaytiriladigan ba’zi konstantalardan tezroq emasligini anglatadi.

Download 45,27 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish