2-bob. Algoritmlarning murakkabligi.
2.1 Algoritmlarning vaqt va hisoblash murakkabligi.
Algoritmning vaqt murakkabligi (T(N) , qayerda N- topshiriqning o'lchami) - qadamlar bilan o'lchanadigan algoritmning bajarilish vaqti (natijaga erishish uchun bajarilishi kerak bo'lgan algoritm ko'rsatmalari). Ya'ni, bu muammoni hal qilish algoritmini tashkil etuvchi elementar operatsiyalar soni (: =,<>, =, +, -, *, /; va, yoki, emas, xor; qo'ng'iroq qilish, qaytish).
Muammoni hal qilishda kiritilgan ma'lumotlarning kombinatsiyasiga (ekvivalentligi, siyrakligi, tartibliligi va kiritilgan ma'lumotlarning boshqa xususiyatlari) bog'liq bo'lgan uch xil vaqt murakkabligi mavjud.
https://pandia.ru/text/78/183/images/image002_151.gif "kenglik =" 178 balandlik = 60 "balandlik =" 60 ">
Bo‘lyapti T(N)= C* N2 kvadrat matritsa uchun amal qiladi.
Bu holda elementar operatsiyalar "+" va "*" kombinatsiyasi hisoblanadi.
Agar asl matritsa identifikatsiya bo'lsa, biz eng yaxshi holatni olamiz.
Agar matritsada elementlarning yarmi 0, yarmi 1 bo'lsa, biz O'rtacha holatni olamiz.
Doimiy BILAN, aniq ifodalab bo'lmaydigan, tashqi omillarning algoritmlarni bajarish vaqtiga ta'sirini tavsiflaydi (kompyuter tezligi, kompilyatsiya tezligi). Shuning uchun algoritmlarning vaqt murakkabligini baholash uchun vaqt birliklaridan foydalanish mutlaqo to'g'ri emas. Bu holda matritsa-vektorni ko'paytirish algoritmining vaqt murakkabligi ga proportsional deyiladi. N2 .
Dostları ilə paylaş: |
