Algoritmlar samaradorligini tahlil qilish

1. Tahlil asoslari Asimptotik tahlil

Kamroq tarqalgan murakkablik funktsiyalari
Bunda qisman O (Big-O) va qisman Ω (Big-Ω) ham bor.
Yani quyidagicha:
Homework:
Soft-O ham mavjud:
Biror narsaning kuchga bo'lgan logarifmi yuqoridan shu narsaning kuchga bog'langanligi sababli, quyidagicha ko`rinishda ham mavjud

1. Tahlil asoslari Asimptotik tahlil

Asimptotik murakkablikni aniqlash
Determining Asymptotic Complexity
Odatda biz kod bo'lagini ko'rishimiz va darhol uning Θ(1), Θ(logn), Θ(n), Θ(nlogn) yoki nima ekanligini "ko'rishingiz" mumkin. Ammo tekshirish orqali aniqlay olmasangiz, T(n) ni olgan holda berilgan kirish o'lchamlari uchun operatsiyalarni hisoblash uchun kod yozishingiz mumkin. Keyin siz f ning turli qiymatlarini "taxmin qilasiz", bu uchun T∈Θ(f). Buni amalga oshirish uchun ko'p turli f va n lar uchun T(n)/f(n) qiymatlarini hosil qiling, bunda nisbat deyarli doimiy bo'lgan f ni qtopishimiz zarur.

1. Tahlil asoslari Asimptotik tahlil

Asimptotik murakkablikni aniqlash
Determining Asymptotic Complexity
Example:

1. Tahlil asoslari Asimptotik tahlil

Asimptotik murakkablikni aniqlash
Determining Asymptotic Complexity
Yuqorida natijalar asosida:
Biz T (n) / n nisbati ortib borayotganini ko'ramiz, shuning uchun murakkablik, ehtimol, chiziqli emas. T(n)/nlogn va T(n)/n2 nisbatlari kamayadi, shuning uchun bu funksiyalar yuqori chegaralardir. Lekin T(n)/nloglogn ham ortadi, lekin o'sish sur'ati sekinlashayotganga o'xshaydi va balkim, ehtimol hatto yaqinlashar. Biz murakkablik ∈Θ(nloglogn) ekanligini ta'kidlashimiz mumkin, biroq aslida biz rasmiy dalil qilishimiz kerak.

1. Tahlil asoslari

Kirish hajmini oshirishning ta'siri
The Effects of Increasing Input Size
Etakchi doimiy omillarni bostirish, algoritmni boshqaradigan kompyuter tezligi kabi amalga oshirishga bog'liq tafsilotlarni yashiradi. Shunday bo'lsa-da, siz doimiy omillarsiz ham ba'zi kuzatishlar qilishingiz mumkin.