Кіріспе

Компьютерлік ғылымдағы әдіс

Компьютерлік ғылымда Акра–Бацци әдісі немесе Акра–Бацци теоремасы математикалық рекурренциялардың асимптотикалық мінез-құлқын талдау үшін қолданылады. Бұл, қосалқы есептердің мөлшері айтарлықтай ерекшеленетін, бөл және басқар (divide and conquer) алгоритмдерін талдауда кездесетін рекурренциялар үшін негізгі теореманың жалпылауы болып табылады, ол қосалқы есептердің мөлшері бірдей деп есептейді. Бұл теорема математиктер Мохамед Акра мен Луай Баццидің есімдерімен аталады. Қолдану шарттары:

жеткілікті базалық жағдайлар берілген,
және барлық үшін тұрақты,
барлық үшін тұрақты,
барлық үшін тұрақты, мұндағы c тұрақты және O – Үлкен O нотациясын білдіреді,
барлық үшін тұрақты.

-ның асимптотикалық мінез-құлқы, -ға тең болатын мәнін анықтау арқылы табылады және сол мәнді теңдеуге қою арқылы:

(Θ қараңыз). Интуитивті түрде, -ның индексіндегі шағын өзгерісті білдіреді. -ның абсолюттік мәні әрқашан 0 мен 1 арасында болатынын ескере отырып, индекстегі ең төменгі функцияны (floor function) ескермеуге болады. Сол сияқты, ең жоғарғы функцияны (ceiling function) да ескермеуге болады. Мысалы, Акра–Бацци теоремасы бойынша, және бірдей асимптотикалық мінез-құлыққа ие болады.

Мысал

Егер бүтін сандар үшін 1 деп, ал бүтін сандар үшін анықталған болса, Акра-Баззи әдісін қолданудағы бірінші қадам – мәнін табу болып табылады, онда . Осы мысалда, . Содан кейін, формула қолданылып, асимптотикалық мінез-құлық мынадай түрде анықталады:

Маңыздылығы

Акра-Бацци әдісі асимптотикалық мінез-құлықты анықтау үшін көптеген басқа техникалардан тиімді, себебі ол өте кең ауқымды жағдайларды қамтиды. Оның негізгі қолданылуы – көптеген «бөліп биле» алгоритмдерінің орындалу уақытын жуықтау. Мысалы, біріктіру сұрыптауында ең нашар жағдайда қажетті салыстырулар саны, орындалу уақытына шамамен пропорционалды, және бүтін сандар үшін рекурсивті түрде келесідей беріледі: және, осылайша Акра-Бацци әдісін қолдану арқылы есептеуге болады.