Алгоритмдерді талдау. Функцияның өсуі. Асимптотикалық белгілер

1.

Дәріс 2. Алгоритмдерді талдау.
Функцияның өсуі. Асимптотикалық
белгілер
Алгоритмдерді жобалау және талдау

2.

Алгоритмдерді талдау (кіріспе)
• Алгоритмдер информатиканың маңызды құрамдас бөлігі болып табылады, өйткені оларды
зерттеу бағдарламалау тілін немесе компьютерді қолдануды қажет етпейді. Бұл
алгоритмдердің тиімділігін оларды жүзеге асырмай салыстыруға мүмкіндік беретін
әдістердің қажеттілігін білдіреді. Бұл құралдардың ішіндегі ең маңыздысы-RAM есептеу
моделі және ең нашар жағдайлардың күрделілігіне асимптотикалық талдау.
• Алгоритмдердің жұмысын бағалау үшін асимптотикалық белгілер қолданылады.

3.

RAM есептеу моделі
• Машиналық тәуелсіз алгоритмдердің дамуы гипотетикалық компьютерге негізделген, ол жадқа еркін
қол жетімді машина (Random Access Machine) немесе RAM машинасы деп аталады. Қарастырылған
RAM моделіне әдетте нақты компьютерлерден табуға болатын командалар кіреді. Осы модельге
сәйкес біздің компьютерле келесідей жұмыс істейді:
• кез-келген қарапайым операцияны орындау үшін ( + ,*, -,=, if, call) дәл бір уақыт кезеңі қажет;
• циклдер мен кіші бағдарламалар қарапайым операциялар болып саналмайды, бірақ бірнеше қарапайым
операциялардан тұрады. Сұрыптау ішкі бағдарламасын бір сатылы операция деп санаудың қажеті жоқ,
өйткені 1 000 000 элементті сұрыптау он элементті сұрыптауға қарағанда әлдеқайда көп уақытты алады.
Циклдің немесе ішкі бағдарламаның орындалу уақыты итерациялардың санына немесе ішкі бағдарламаның
нақты сипатына байланысты болады;
• жадқа әр қадам бір уақытты алады. Сонымен қатар, біздің компьютерде шексіз жедел жады бар. RAM
моделіндегі Кэш пен диск қолданылмайды

4.

RAM моделі
• RAM моделіндегі алгоритмнің орындалу уақыты мәселенің осы данасын шешу үшін алгоритмге қажет
қадамдардың жалпы санына сәйкес есептеледі. Біздің RAM машинамыз секундына белгілі бір
қадамдар/операцияларды орындауға мүмкіндік бере отырып, қадамдар санын уақыт бірліктеріне
аудару оңай
• Бұл RAM моделі компьютерлердің жұмысын тым қарапайым түрде көрсететін сияқты.. Ақыр соңында,
көптеген процессорларда екі санды көбейту қосуға қарағанда көп уақытты алады, бұл модельдің
алғашқы болжамына сәйкес келмейді. Екінші болжамды циклды компилятордың сәтті оңтайландыруы
немесе процессордың гиперпоток мүмкіндігі бұзуы мүмкін. Ақыр соңында, деректерге қол жеткізу
уақыты деректердің орналасуына байланысты айтарлықтай өзгеруі мүмкін: кэште, жедел жадта
немесе дискіде. Осылайша, нақты компьютермен салыстырғанда, RAM машинасы үшін барлық үш
негізгі болжам дұрыс емес.
• Алайда, осы компьютерге сәйкес келмеуіне қарамастан, RAM моделі алгоритмнің нақты компьютерде
қалай жұмыс істейтінін түсіну үшін керемет модель болып табылады. (нақты компьютер сияқты жұмыс
жасауы және қарапайымдылығы.)

5.

Ең жақсы, ең нашар және орташа
жағдайдың күрделілігін талдау
• RAM моделін қолдана отырып, тапсырманың кезкелген данасын орындау үшін алгоритмге қажет
қадамдар санын есептеуге болады. Алгоритмнің
қаншалықты жақсы немесе жаман екендігі туралы
жалпы түсінік алу үшін біз оның тапсырманың
барлық даналарымен қалай жұмыс істейтінін
білуіміз керек. Алгоритмнің күрделілігінің ең жақсы,
ең нашар және орташа жағдайы нені білдіретінін
түсіну үшін (яғни, оны тиісті жағдайда орындау
уақыты), алгоритмнің орындалуын барлық мүмкін
даналарда қарастыру қажет.
• Ең нашар, ең жақсы және орташа жағдайдағы
қиындықтар (кез-келген n кіріс данасын өңдеуге
арналған қадамдар санына байланысты)

6.

Асимптотикалық белгілерге кіріспе
• Алгоритмнің жұмыс уақытының Өсу реті сияқты шаманы бағалау үшін жеткілікті үлкен көлемдегі
кірістерді қарастыра отырып, біз алгоритмдердің асимптотикалық тиімділігін зерттейміз. Бұл бізді
алгоритмнің жұмыс уақыты кіріс көлемінің ұлғаюымен қалай өсетіні қызықтырады дегенді білдіреді.
Әдетте асимптотикалық мағынада тиімдірек алгоритм кейбір кішкентайларды қоспағанда, барлық
енгізулер үшін тиімді болады.

7.

Асимптотикалық белгілер (не үшін қажет?)
• Кез-келген алгоритм үшін ең жақсы, ең нашар және орташа жағдайдың уақыт күрделілігі мәселенің мүмкін даналарының
өлшемдерінен сандық функция ретінде ұсынылуы мүмкін. Бірақ бұл функциялармен жұмыс істеу өте қиын, өйткені олар
келесі қасиеттерге ие:
• тым толқынды. Кез-келген алгоритмнің уақыт күрделілігінің нақты функциясы ұсақ бұдырлар мен ойыс біркелкі емес графикке ие
болуы мүмкін. Шекаралар N> n0 кезінде жарамды
• дәл анықтау үшін тым көп ақпарат қажет. Ең нашар жағдайда орындалатын RAM машинасының нұсқауларының нақты санын есептеу
үшін алгоритм толық компьютерлік бағдарламаның егжей-тегжейлі жазылуы керек. Сонымен қатар, жауаптың дәлдігі кодтаудың
маңызды емес бөлшектеріне байланысты (мысалы, кірістірілген if операторларының орнына case операторы қолданылған ба ). Ең
нашар жағдайды дәл талдау, мысалы:
Т(n) = 13252