Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Есептердің алгоритмдік күрделілілігін өлшеу



Күрделілілік тұрғысынан алгоритмдердің екі үлкен класы бар - қайталауы бар алгоритмдер және рекурсивті алгоритмдер.Бір есепті көптеген алгоритммен шешуге болады. Олардың әрқайсысының жұмысының тиімділігі әртүрлі сипаттаулармен сипатталады. Алгоритмді талдамас бұрын ең алдымен берілген алгоритм есепті дұрыс шешетінін дәлелдеуіміз керек. Егер есепті дұрыс шешпесе тиімділік мәселесінің мәні жоқ. Егер алгоритм қойылған есепті шешсе, оның қаншалықты тиімді екенін қарастыруымыз керек. Сондықтан оның тиімділігінін анықтау үшін алгоритмдерді талдауымыз қажет.

Қайталау алгоритмінің негізінде шартты өрнектер мен цикл жатыр; мұндай алгоритмдерді талдауда циклдын ішінде қолданылатын операция саны мен цикл итерациясының санын бағалау керек. Рекурсивтік алгоритмдер үлкен есепті фрагменттерге бөледі және әрбір фрагменттерді жеке қолдануға мүмкінлік береді. Осындай алгоритмдерді кейде «бөліп алда біле» алгоритмі деп айтайды және оларды қолдану өте тиімді болуы мүмкін. Үлкен есептердікішіге бөлу жолымен шешу үрдісінде үлкен емес, қарапайым және түсінікті алгоритм құрылады. Рекурсивті алгоритмді талдауда есепті бөлімге бөлуге қажетті операцияның санын санау, ірбңр бөлімдегі алгоритмнің орындалуы және есепті толық шешудегі әрбір бөлімнің нәтижесін біріктіру керек. Осы ақпараттарды және неше бөлік екенінің саны, олардың өлшемінен алгоритмнің күрделілігінің рекуррентік қатынасын шығарамыз.

Алгоритмдерді әртүрлі белгілер бойынша жіктеуге болады. Мысалы, жалпы комбинаторлық алгоритмдер, тағы алгоритмдер, максимальды ағынды іздеу алгоритмдері, максимальды жұп сәйкестігін іздеу алгоритмдері, іздеу алгоритмдері, Алгоритмы на строках, жолды іздеу алгоритмдері, Бұтақтармен жұмыс алгоритмдері, сұрыптау алгоритмдері, сығу алгоритмдері, үлестірілген жүйелер алгоритмдері, операциялық жүйелердегі алгоритмдер, тиімділеу алгоритмдері және т.б.

Есептеу моделіне байланысты сандық, логикалық, продукциялық, нейрожелілік, параллель, полиномдық, құмырсқа, генетикалық және т.б. бөлінеді.





Дата публикования: 2015-01-04; Прочитано: 1319 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...