Fan: Algoritimlarni loyihalash

Priori tahlili — algoritmning nazariy tahlili. Algoritmning samaradorligi boshqa barcha omillar, masalan protsessor tezligi doimiy boʻlib, uni amalga oshirishga hech qanday taʼsir koʻrsatmaydi deb taxmin qilish orqali oʻlchanadi.
Posterior tahlili — algoritmning empirikal tahlili hisoblanadi. Tanlangan algoritm dasturlash tili yordamida amalga oshiriladi. Keyin maqsad kompyuter mashinasida bajariladi. Ushbu tahlilda ish vaqti hamda fazo kabi haqiqiy statistika toʻplangan.
Biz priori algoritm tahlili haqida bilib olamiz. Algoritmni tahlil qilish turli xil operatsiyalarning bajarilishi yoki bajarilish vaqti bilan bogʻliq. Ishlashning davomiyligi har bir operatsiyada bajarilgan kompyuterning koʻrsatmalar soni sifatida aniqlanishi ham mumkin.
Algoritmning murakkabligi Aytaylik, X — algoritm va n — kirish maʼlumotlarining hajmi, X algoritmi tomonidan ishlatiladigan vaqt va makon X ning samaradorligini belgilovchi ikkita asosiy omildir.
• Vaqt faktori — vaqt saralash algoritmidagi taqqoslash kabi muhim operatsiyalar sonini hisoblash bilan oʻlchanadi.
• Fazo faktori — fazo, algoritm tomonidan talab qilinadigan maksimal xotira fazosini hisoblash bilan oʻlchanadi.
f(n) algoritmining murakkabligi ish vaqti va / yoki algoritm tomonidan talab qilinadigan xotira fazosi kirish maʼlumotlarining hajmi sifatida n nuqtai nazaridan talab qiladi.
Fazo murakkabligi
Algoritmning fazo murakkabligi uning hayotiy siklida algoritm talab qiladigan xotira fazosi miqdorini anglatadi. Algoritm tomonidan talab qilinadigan fazo quyidagi ikkita komponentning yigʻindisiga teng:
• Muammo hajmidan mustaqil boʻlgan maʼlum maʼlumotlar va oʻzgaruvchilarni saqlash uchun zarur boʻlgan fazo. Masalan, ishlatiladigan oddiy oʻzgaruvchilar va konstantalar, dastur hajmi va boshqalar.
• Oʻzgaruvchan qism — oʻzgaruvchilar tomonidan talab qilinadigan fazo boʻlib, ularning oʻlchamlari muammoning hajmiga bogʻliq. Masalan, dinamik xotirani ajratish, recursion stack fazo va boshqalar.
Har qanday algoritmning S(P) fazo murakkabligi S(P) = C + SP(I), bu yerda C — tuzalgan (fixed) qism, S(I) esa algoritmning oʻzgaruvchan qismidir, bu I misolning xarakteristikasiga bogʻliq. Hozirgi narsani tushuntirishga harakat qiladigan oddiy misol:
Algoritm: SUM(A, B)
1—qadam — BOSHLASH
2—qadam — C ← A + B + 10
3—qadam — TOʻXTASH
Bu yerda biz uchta oʻzgaruvchini A, B va C hamda bitta konstantani olamiz. Demak, S(P) = 1 + 3. Endi fazo berilgan oʻzgaruvchilar maʼlumotlar turiga va konstanta turlarga bogʻliq va shunga mos ravishda koʻpaytiriladi.
Vaqt murakkabligi
Algoritmning vaqt murakkabligi algoritmni bajarishga zarur boʻlgan vaqt miqdorini anglatadi. Vaqt talablari T(n) raqamli funksiya sifatida aniqlanishi mumkin, bunda har bir qadam doimiy vaqtni talab qilganda, T(n) bosqichlar soni sifatida oʻlchanishi mumkin.
Masalan, ikkita n—bitli butun sonni qoʻshish n bosqichni oladi. Demak, umumiy hisoblash vaqti T(n) = c ∗ n, bu yerda c — ikkita bit qoʻshilishi uchun olingan vaqt. Bu yerda biz T(n) kirish hajmi kattalashganda chiziqli oʻsishini kuzatamiz.
Xulosa: 1.A grafik - bu ikkilik munosabatlarga ega bo'lgan vertexlar guruhi. Bir-biriga bog'langan tugunlar to'plamini o'z ichiga olgan ma'lumotlar tuzilishi daraxt deb nomlanadi.
2.Haqiqiy hayot daraxtiga o'xshab, uning tuzilishi bir-biriga bog'langan tugunlarni o'z ichiga oladi. Har bir tugun ma'lum bir qiymatga yoki shartga ega bo'lishi mumkin. Daraxt ham yakka o'zi turishi yoki alohida ma'lumotlar tuzilishini anglatishi mumkin.
3. Grafiklar daraxtlar bilan bir xil tugunlar va qirralarning guruhidan iborat, ammo grafikalar mavjud bo'lsa, tugunlar orasidagi ulanish uchun qoidalar mavjud emas.
4.Grafda uchta to'plam mavjud; bular vertekslar, qirralar va qirralar orasidagi munosabatlar o'rnida o'rnatilgan.
5. Daraxt har qanday ko'chadan bo'lmasligi mumkin va u hali ham ulanishi mumkin. Bunga qo'shimcha ravishda, u kamtarona bog'langan grafik deb nomlanadi, unda ikkita tepani bir-biriga bog'laydigan bitta yo'l mavjud
6.Hamma mavjud bo'lgan daraxtlar grafikalardir.