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