Algoritmlar samaradorligini tahlil qilish

1. Tahlil asoslari

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.
Algoritmning murakkabligi

1. Tahlil asoslari

Algoritmning fazoviy va vaqtinchalik murakkabligini o'lchash yoki hech bo'lmaganda to'g'ri bayonotlar berish muhimdir. Bu sizga hal qilishingiz kerak bo'lgan muammoga ikkita muqobil yondashuvning afzalliklarini solishtirish, shuningdek, kodlash uchun pul va vaqtni sarflashdan oldin taklif qilingan yechim kerakli resurs cheklovlariga javob berishini aniqlash imkonini beradi.
fazoviy va vaqtinchalik

1. Tahlil asoslari

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.

1. Tahlil asoslari

Vaqt murakkabligi
Algoritmning mutlaq ishlash vaqtini oldindan aytib bo‘lmaydi, chunki u algoritmni amalga oshirish uchun foydalaniladigan dasturlash tiliga, dastur ishlayotgan kompyuterga, bir vaqtning o‘zida ishlaydigan boshqa dasturlarga, operatsion tizimning sifatiga va ko‘pgina omillarga bog‘liq. boshqa omillar. Bizga algoritmning ishlash vaqti haqida mashinadan mustaqil tushuncha kerak.