Asimptotik notatsiya

O’tgan maqolalarimizda
asimptotik analiz va eng yaxshi,o’rta va eng yomon holatlar haqida gaplashgan edik. Demak, asimptotik analizning asosiy g’oyasi algoritmning vaqt bo’yicha samaradorligini o’lchashda konstantaga e’tibor bermaslik, shu bilan birga algortimning samaradorligini bilish uchun uni kodga o’girishga hojat yo’qligidir.

Aytaylik, chiziqlik qidiruv algoritmni vaqt bo’yicha samaradorligi
T(c) = cn edi. Asimptotik analizga ko’ra ushbu formuladagi c ni e’tiborga olmasligimiz va vaqt samaradorligini T(c) = n deb qabul qilib olishimiz kerak.

Bugungi maqolamizda esa algoritmlarni vaqt bo’yicha murakkabligini hisoblashda asimptotik analizning matematik yordamchilari
asimptotik notatsiyalar haqida so’z yuritamiz. 3 xil asimptotik notatsiya mavjud, quyida ularga qisqacha tuxtalib o’tamiz.

Berilgan notatsiyalar bir qarashda qiyindek tuyuladi, eng yaxshi va eng yomon holatlarni ko’z oldingizga keltirsangiz tushunishga oson bo’ladi. Keyinga maqolalarimizda notatsiyalar bo’yicha misollar keltirishga xarakat qilamiz.

Manba:

Ulug’bek Normatov