Algoritm va ularning ta’riflari
+2+3+…+n gacha bo’lgan natural sonlar yig’indisini hisoblash dasturi
Download 69.45 Kb. Pdf ko'rish
|
1-maruza (1)
- Bu sahifa navigatsiya:
- Algoritmlarning murakkabligi Algoritmlarning murakkabligi
- Abstract malumotlar strukturasi - Stack yordamida 1 dan n gacha natural
|
1+2+3+…+n gacha bo’lgan natural sonlar yig’indisini hisoblash dasturi
Algoritmlarning murakkabligi 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. • Abstract ma'lumotlar strukturasi - Stack yordamida 1 dan n gacha natural Download 69.45 Kb. Do'stlaringiz bilan baham: 
|