Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
dain algoritm dina.docx
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
443 Кб
Скачать
☆
  1. Пирамидалық сұрыптау

Пирамидалық сұрыптау Дж. Уильямспен 1964 жылы ұсынылды. Бұл сұрыптауға керекті қосымша жад көлемі берілген деректердің көлеміне тәуелді емес. Алгоритмнің орындалу уақыты - O(n * log n). Алгоритмнің идеясы:

Пирамида – әрбір элементтің оған еншілес элементке мәні тең не үлкен болатын екілік ағаш. Ағашты солдан оңға қарай ретпен элементтермен толтырып, оны пирамидаға жеңіл сұрыптап алып айналдыруға болады. Пирамиданың ең үлкен элементі оның ұшында орналасады. Одан кейін пирамиданың ұшындағы элементпен массивтің соңғы элементі орын ауысады(өсу ретімен болғанда). Сөйтіп, массив артынан бастап сұрыпталады(оңнан солға қарай). Астындағы(еншілес) элементтер үстіндегі элементпен салыстырылып орын ауысады. Сөйтіп, ұшына екінші ең үлкен элемент келіп орналасады. Солайша сол ұшындағы үлкен элементті массивтің соңғы элементтінен кейінгі элементпен орын ауыстырамыз, өйткені ақырғы элемент сұрыпталып қойған. Сөйтіп массив элементтері оңнан солға қарай сұрыпталады.

Жақсы жақтары:

  • O(n * log n) нашар жағдайының дәлелденген бағасы бар;

  • Орнында сұрыптайды(пирамидалық сұрыптау – ішкі сұрыптаудың бір түріне жатады, ал ішкі сұрыптауда массивтер оперативті жадыда толығымен орналасады), яғни қосымша жадыны қажет етпейді

Жаман жақтары:

  • Орындалуы ауыр;

  • Сұрыпталуға жақын массивте хаосты деректертерді сұрыптағандай ұзақ;

  • Орнықсыз(неустойчив) – орнықтылығын қамтамассыз ету үшін кілтті кеңейту керек;

  • Әдіске тікелей рұқсат(доступ) керек, тізбекті рұқсатты қажет ететін тізіммен және басқа да жады құрылымдармен жұмыс істей алмайды

Қорытынды: алгоритмді орындау қиындығынан, оны тек үлкен көлемді n-де қолданған жөн. Үлкен емес n көлемді(бірнеше мыңға дейін) массивта Шелл сұрыптауы жылдамырақ.

  1. Сараң алгоритмдердің күрделілігін бағалау.

Сараң алгоритмдер– алгоритмнің әрбір кезеңінде локальді оптимальді шешімдерді қабылдауға негізделетін алгоритм. Сонымен бірге ең соңғы шешім де оптимальді шығуы мүмкіндігін ұйғарады.

«Әр қадамда максимальды ұтыс» қағида бойынша істейтін алгоритмдер сараң (градиентті) алгоритмдер деп аталады. Осы тәріздес ең танымал есептердің бірі - оптимальді қаңқа туралы есеп.

Қолданылу шарттары: сараң алгоритмдер қолданатын есептерге екі ерекшелік тән: біріншіден, оларға сараң таңдау қағидасы қолдануға болады, екіншіден, олар қосалқы есептер үшін оптималдылық қасиетіне ие болады

Сараң таңдау қағидасы

Егер локальді оптимальді таңдаулар тізбегі глобальді оптимальді шешімін берсе, онда оптимизацилық есепке сараң таңдау қағидасын қолдануға болады. Әдеттегі жағдайда оптималдылықтың дәлелі келесі схемаға сәйкес болады: алдымен, сараң таңдау бірінші қадамда оптимальді шешімге келуге кедергі жасамайды екендігі дәлелденеді: әрбір шешімге сәйкес сараң таңдаумен үйлесімді және бірінші шешімнен жаман емес басқа шешім бар. Содан кейін, сараң таңдаудың бірінші қадамынан соң пайда болатын қосалқы есеп бастапқы есепке ұқсас екендігі көрсетіледі және пікір индукция бойынша бітеді.

Сараң алгоритмдердің тиімді шешім бермейтін есептері

NP класына жататын есептер қатары сараң алгоритмдер оптималды шешім бермейді. Оларға келесілер жатады:

  • Коммивояжер есебі;

  • Графтың минималды суреттеу есебі;

  • Графты қосалқы графқа бөлу есебі

  • Максималды кликті бөлу есебі

  • Кестені құрумен байланысты есептер

Дегенмен кейбір есептерде сараң алгоритмдер жаман емес жақын шешім береді.

Алгоритмдердің күрделілігін бағалау үшін қолданылатын функциялардың кластары

Төменде қолданылған алгоритмдердің күрделілігін бағалайтын барлық функциялар табиғи аргументтің теріс емес асимптотикалық функциясы деп есептеледі, аргументінің кейбір мәнінен бастап.

Асимптотикалық бағалау үшін жоғары жағынан функцияның классы қолданылады

Асимптотикалық бағалау үшін төменгі жағынан функцияның классы қолданылады

Асимптотикалық нақты бағалау үшін функцияның классы қолданылады

Келесі қатынастар орынды болып келеді

Ары қарай стандартты функцияларды білу қажет, оларды қиындылықты бағалау кезінде білу қажет. Полиномдар, экспоненттер, суперэкспоненттер, логарифмдер, суперлогарифмдер, факториалдар, Фибоначчи сандары. Өсу шапшаңдығы бойынша салыстыру меңзелінеді.

.Қолданылу шарттары: сараң алгоритмдер қолданатын есептерге екі ерекшелік тән: біріншіден, оларға сараң таңдау қағидасы қолдануға болады, екіншіден, олар қосалқы есептер үшін оптималдылық қасиетіне ие болады. Жоғары және төменгі бағалауды және орташа бағалауды алу үшін амортизациялық бағалаулар жиі қолданылады.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]