Maʼlumotlar tuzilmasida algoritmlarni tuzish qoidasi. Reja: Algoritm

Algoritm tahlili
Algoritmning samaradorligi ikki xil bosqichda, amalga oshirishdan oldin va amalga oshirilgandan keyin tahlil qilinishi mumkin. Ular quyidagilar:
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.