#pragma argsused #include #pragma hdrstop #include

Tahlil turlari

Berilgan algoritmni tahlil qilishimiz uchun biz algoritm qaysi berilganlar to'plami bilan kam vaqt talab etadi va qaysi berilganlar to’plami bilan algoritm uzoq vaqt talab qilishligini bilishimiz kerak.

Algoritmni ifoda sifatida ko'rsatish mumkinligini biz allaqachon ko'rdik . Bu shuni anglatadiki, biz bir nechta ifodalar bilan algoritmni taqdim etamiz: biri kamroq vaqt talab qiladigan holat uchun, ikkinchisi esa ko'proq vaqt talab qiladigan holat uchun .

Odatda, birinchisi algoritmning eng yaxshi holati, ikkinchisi esa eng yomon holat deb nomlanadi .

Algoritmni tahlil qilish uchun qandaydir qoida kerak bo’ladi, qaysiki asimtotik tahlil uchun asos yaratadi.

Uch xil tahlil mavjud:

• Eng yomon holat

○ Algoritm eng ko'p vaqt talab qiladigan berilganlar to'plamini aniqlaydi (bajarish uchun eng uzoq vaqt).

• Eng yaxshi holat

○ Algoritm eng kam vaqtni (bajarish uchun eng tez vaqt) talab qiladigan berilganlar to'plamini aniqlaydi .

• O'rta holat

○ Algoritmning ishlash vaqtini taxmin qilishni ta'minlaydi.

○ Algoritm ko'p marta turli xil kirish berilganlaridan foydalangan holda ishlaydi . 

○ Berilganlarning ba'zi bir umumiy guruhidan kirish berilganlarining test to'plamlari tanlanadi va algoritmning umumiy ishlash vaqti hisoblanadi, so'ngra testlar soniga bo'linadi .

○ Kirish berilganlari tasodifiy tanlanadi.

 Quyi chegara <= O'rtacha vaqt <= Yuqori chegara

 Berilgan algoritm uchun biz eng yaxshi, yomon va o'rtacha holatlarni ifoda sifatida taqdim eta olamiz . Masalan, berilgan algoritmni ifodalovchi funktsiya f (n) bo'lsin .

f ( n ) n²  + 500 Eng yomon holat

f ( n ) n + 100n   500  Eng yaxshi holat

f ( n ) n² /2   50n  + 500  O’rta holat