«Информатиканың теориялық негіздері»
Еңбеккөлемділік функциясының түрі бойынша алгоритмдер классификациясы
жүктеу/скачать 0,68 Mb.
|
«Информатиканы теориялы негіздері»
Еңбеккөлемділік функциясының түрі бойынша алгоритмдер классификациясыБастапқы мәліметтердің алгоритмнің еңбеккөлемділігінің функциясына әсеріне байланысты алгоритмдер анализі үшін практикалық маңызы бар келесі классификация ұсынылады: 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,68 Mb. Достарыңызбен бөлісу:
|