Kompyuter arxitekturasi” Fanidan Mustaqil ishi

Asimptotik tahlil
Algoritmning murakkabligi yoki samaradorligi - bu algoritm tomonidan kerakli natijani olish uchun bajariladigan qadamlar soni. Asimptotik tahlil algoritmni nazariy tahlil qilishda uning murakkabligini hisoblash uchun amalga oshiriladi. Asimptotik tahlilda algoritmning murakkablik funksiyasini hisoblash uchun kiritishning katta uzunligidan foydalaniladi.
Eslatma - Asimptotik - bu chiziq egri chiziqqa to'g'ri keladigan, lekin ular kesishmaydigan holat. Bu erda chiziq va egri chiziq bir-biriga asimptotikdir.
Asimptotik belgilar yuqori va past tezlik chegaralaridan foydalangan holda algoritmning eng tez va eng sekin bajarilish vaqtini tasvirlashning eng oson usuli hisoblanadi. Buning uchun biz quyidagi belgilardan foydalanamiz -
Katta O belgisi
Omega belgisi
Teta belgisi
Katta O belgisi
Matematikada Big O belgisi funksiyalarning asimptotik xarakteristikalarini ifodalash uchun ishlatiladi. Bu oddiy va aniq usulda katta kirishlar uchun funksiyaning harakatini ifodalaydi. Bu algoritmning bajarilish vaqtining yuqori chegarasini ifodalash usuli. Bu algoritm bajarilishini yakunlashi mumkin bo'lgan eng uzoq vaqtni ifodalaydi. Funktsiya -

f(n) = O(g(n))
c va n0 musbat konstantalar mavjud bo'lsa, f(n) ≤ c * g(n) n ≥ n0 bo'lgan barcha n uchun.
Omega belgisi
Omega yozuvi algoritmning bajarilish vaqtining pastki chegarasini ifodalash usulidir. Funktsiya -
f(n) = Ō (g(n))
agar c va n0 musbat konstantalar mavjud bo'lsa, n ≥ n0 bo'lgan barcha n uchun f(n) ≥ c * g(n) bo'ladi.
Theta notation
Teta yozuvi algoritmning bajarilish vaqtining pastki chegarasini ham, yuqori chegarasini ham ifodalash usulidir. Funktsiya -
f(n) = th(g(n))
agar c1, c2 va n0 musbat konstantalar mavjud bo'lsa, c1 * g(n) ≤ f(n) ≤ c2 * g(n) barcha n uchun bu erda n ≥ n0.
Algoritmni tezlashtirish
Parallel algoritmning ishlashi uning tezligini hisoblash yo'li bilan aniqlanadi. Tezlik ma'lum bir muammo bo'yicha eng tez ma'lum bo'lgan ketma-ketlik algoritmining eng yomon holatda bajarilishi vaqtining parallel algoritmning eng yomon bajarilish vaqtiga nisbati sifatida aniqlanadi.
tezlashtirish =
Muayyan muammo uchun eng tez ma'lum bo'lgan ketma-ketlikning eng yomon bajarilish vaqti / Parallel algoritmning eng yomon holatini bajarish vaqti