Алгоритм анализіндегі белгілеу жүйелері
Алгоритмнің еңбеккөлемділігін бөлшектеп талдау кезінде N ұзындықты бір кірісте орындалатын элементар амалдар саны тура осындай ұзындықты келесі кірістегі амалар санымен үнемі сәйкес келе бермейтіні белгілі болды. Бұл осы алгоритмнің бектіліген ұзындықты кіріс берілгендерінде еңбеккөлемділік функциясының мінезін бейнелейтін арнайы белгілеулер енгізу қажеттігіне алып келеді.
Айталық, – осы есептің нақты мәселелерінің формальды жүйеде берілген жиыны болсын. Айталық, D є – нақты мәселенің тапсырмасы болсын және |D| = N.
Жалпы жағдайда жиынының барлық нақты мәселелерді қамтитын, N қуаты бар жеке ішкі жиыны болады:
Осы ішкі жиында : = {D є ,: |D| = N} арқылы белгілейік;
Сонда осы алгоритм N өлшемді әртүрлі есептерді шеше отырып, қандай-да бір жағдайда неғұрлым саны көбірек амал орындайды, қандай-да бір жағдайда неғұрлым саны азырақ көбірек амал орындайды. Келесі белгілеулерді енгізейік:
(N) – ең нашар жағдай – N өлшемді нақты мәселелерді шешуге арналған А алгоритмінің неғұрлым көбірек амал саны: - - ге ең нашар жағдай
(N) – ең жақсы жағдай – N өлшемді нақты мәселелерді шешуге арналған А алгоритмінің неғұрлым азырақ амал саны: – -ге ең жақсы жағдай
(N) – орташа жағдай – N өлшемді нақты мәселелерді шешуге арналған А алгоритмінің орташа амал саны:
– -ге орташа жағдай
Достарыңызбен бөлісу: | 
