«Информатиканың теориялық негіздері»


Еңбеккөлемділік функциясының түрі бойынша алгоритмдер классификациясы



бет44/80
Дата07.01.2022
өлшемі0.6 Mb.
#20727
1   ...   40   41   42   43   44   45   46   47   ...   80

Еңбеккөлемділік функциясының түрі бойынша алгоритмдер классификациясы


Бастапқы мәліметтердің алгоритмнің еңбеккөлемділігінің функциясына әсеріне байланысты алгоритмдер анализі үшін практикалық маңызы бар келесі классификация ұсынылады: 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 массивіндегі максимумды іздеу алгоритмін қарастырайық.



(орындалған меншіктеу операторларының саны массив элементтерінің ілесі ретіне байланысты)


  1. Достарыңызбен бөлісу:
1   ...   40   41   42   43   44   45   46   47   ...   80




©emirsaba.org 2022
әкімшілігінің қараңыз

    Басты бет