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

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

(D) = (|D|) = (N)

Сандық-тәуелді еңбеккөлемділік функциясы бар алгоритмдерге массивтер және матрицалармен стандартты амалдарға – матрицаларды көбейту, матрицаларды векторларға көбейту және т.б. - арналған алгоритмдер мысал бола алады.

2.Еңбеккөлемділігі бойынша параметрлі-тәуелді алгоритмдер

Бұл еңбеккөлемділігі кірістің өлшемімен емес(әдетте, осы топ үшін кіріс өлшемі әдетте бекітілген болады), жадының өңделетін сөздерінің нақты мәндерімен анықталатын алгоритмдер:

(D) = (,…,) = (,…,), m =< n

Еңбеккөлемділігі бойынша параметрлі-тәуелді алгоритмдерге сәйкес дәрежелік қатарларды есептеу арқылы берілген дәлдікті стандартты функцияларды есептеу мысал болады. Әлбетте, мұндай алгоритмдер кірісінде екі сандық мәнге ие бола отырып – функция аргументі және дәлдікті – мәнге нағыз амалдар санын орындайды.

а) Тізбектей көбейту арқылы есептеу (x, k) = (k).

б) = (/n!) есептеу, = (x, )дейінгі дәлдікпен.

Дегенмен, көпшілік практикалық жағдайларда еңбеккөлемділік функциясы кірістегі мәліметтердің санына да, сол сияқты кіріс мәліметтерінің мәндеріне де тәуелді болады, бұл жағдайда:

(D) = (||D||, ,…,) = (N, ,…, )

Мысал ретінде параметрлі-тәуелді сыртқы цикл дәлдігі бойынша өлшемді сандық-тәуелді фрагментті қамтитын сандық әдістердің алгоритмдерін келтіруге болады.

Параметрлі-тәуелді алгоритмдер әртүрлілігінің ішінде амалдарының саны бастапқы объектілерінің орналасу ретіне тәуелді болатын тағы да бір топты ерекшелейік.

Айталық, D жиыны келесі элементтерден тұрсын (,…,), және ||D||=N,

Определим = {( ,…,)}- ,…, -дан барлық реттелген N жиынын анықтайық. Мұндағы ||=n!.

3. 
   
   жүктеу/скачать 0,6 Mb.
   
   Достарыңызбен бөлісу: