«Информатиканың теориялық негіздері»
Алгоритм анализіндегі белгілеу жүйелері
жүктеу/скачать 0.6 Mb.
|
- Бұл бет үшін навигация:
- Еңбеккөлемділік функциясының түрі бойынша алгоритмдер классификациясы
Алгоритм анализіндегі белгілеу жүйелеріАлгоритмнің еңбеккөлемділігін бөлшектеп талдау кезінде N ұзындықты бір кірісте орындалатын элементар амалдар саны тура осындай ұзындықты келесі кірістегі амалар санымен үнемі сәйкес келе бермейтіні белгілі болды. Бұл осы алгоритмнің бектіліген ұзындықты кіріс берілгендерінде еңбеккөлемділік функциясының мінезін бейнелейтін арнайы белгілеулер енгізу қажеттігіне алып келеді. Айталық, – осы есептің нақты мәселелерінің формальды жүйеде берілген жиыны болсын. Айталық, D є – нақты мәселенің тапсырмасы болсын және |D| = N. Жалпы жағдайда жиынының барлық нақты мәселелерді қамтитын, N қуаты бар жеке ішкі жиыны болады: Осы ішкі жиында : = {D є ,: |D| = N} арқылы белгілейік; Сонда осы алгоритм N өлшемді әртүрлі есептерді шеше отырып, қандай-да бір жағдайда неғұрлым саны көбірек амал орындайды, қандай-да бір жағдайда неғұрлым саны азырақ көбірек амал орындайды. Келесі белгілеулерді енгізейік: (N) – ең нашар жағдай – N өлшемді нақты мәселелерді шешуге арналған А алгоритмінің неғұрлым көбірек амал саны: - - ге ең нашар жағдай (N) – ең жақсы жағдай – N өлшемді нақты мәселелерді шешуге арналған А алгоритмінің неғұрлым азырақ амал саны: – -ге ең жақсы жағдай (N) – орташа жағдай – N өлшемді нақты мәселелерді шешуге арналған А алгоритмінің орташа амал саны: – -ге орташа жағдай Еңбеккөлемділік функциясының түрі бойынша алгоритмдер классификациясыБастапқы мәліметтердің алгоритмнің еңбеккөлемділігінің функциясына әсеріне байланысты алгоритмдер анализі үшін практикалық маңызы бар келесі классификация ұсынылады: 1.Еңбеккөлемділігі бойынша сандық-тәуелді алгоритмдер Бұл еңбеккөлемділік функциясы нақты кірістің өлшеміне ғана тәуелді болып, және де нақты мәндерден тәуелсіз болатын алгоритмдер: (D) = (|D|) = (N) Сандық-тәуелді еңбеккөлемділік функциясы бар алгоритмдерге массивтер және матрицалармен стандартты амалдарға – матрицаларды көбейту, матрицаларды векторларға көбейту және т.б. - арналған алгоритмдер мысал бола алады. 2.Еңбеккөлемділігі бойынша параметрлі-тәуелді алгоритмдер Бұл еңбеккөлемділігі кірістің өлшемімен емес(әдетте, осы топ үшін кіріс өлшемі әдетте бекітілген болады), жадының өңделетін сөздерінің нақты мәндерімен анықталатын алгоритмдер: (D) = ( ,…, ) = ( ,…, ), m =< n Еңбеккөлемділігі бойынша параметрлі-тәуелді алгоритмдерге сәйкес дәрежелік қатарларды есептеу арқылы берілген дәлдікті стандартты функцияларды есептеу мысал болады. Әлбетте, мұндай алгоритмдер кірісінде екі сандық мәнге ие бола отырып – функция аргументі және дәлдікті – мәнге нағыз амалдар санын орындайды. а) Тізбектей көбейту арқылы есептеу (x, k) = (k). б) = ( /n!) есептеу, = (x, )дейінгі дәлдікпен. 3. Еңбеккөлемділігі бойынша сандық-параметрлі алгоритмдер Дегенмен, көпшілік практикалық жағдайларда еңбеккөлемділік функциясы кірістегі мәліметтердің санына да, сол сияқты кіріс мәліметтерінің мәндеріне де тәуелді болады, бұл жағдайда: (D) = (||D||, ,…, ) = (N, ,…, ) Мысал ретінде параметрлі-тәуелді сыртқы цикл дәлдігі бойынша өлшемді сандық-тәуелді фрагментті қамтитын сандық әдістердің алгоритмдерін келтіруге болады. 3.1 Еңбеккөлемділігі бойынша реттік-тәуелді алгоритмдер Параметрлі-тәуелді алгоритмдер әртүрлілігінің ішінде амалдарының саны бастапқы объектілерінің орналасу ретіне тәуелді болатын тағы да бір топты ерекшелейік. Айталық, D жиыны келесі элементтерден тұрсын ( ,…, ), және ||D||=N, Определим = {( ,…, )}- ,…, -дан барлық реттелген N жиынын анықтайық. Мұндағы | |=n!. Егер (i ) (j ), мұндағы i , j є , онда алгоритмді еңбеккөлемділігі бойынша реттік-тәуелді деп атаймыз. Мұндай алгоритмдердің мысалдары ретінде бірқатар сорттау. Массивтегі минимум және максимумды іздеу алгоритмдері жатады. n элементтен тұратын S массивіндегі максимумды іздеу алгоритмін қарастырайық.
жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|