Алгоритмдерді ресурстар бойынша талдау

Кіріспе

Алгоритмдер қолданатын ресурстарды зерттеу

Компьютерлік ғылымда алгоритмдерді талдау – алгоритмдердің есептеу күрделілігін анықтау процесі, яғни оларды орындау үшін қажетті уақыт, жад немесе басқа да ресурстар мөлшерін табу. Әдетте, бұл алгоритмнің кіріс көлемі мен оның қадамдарының саны (уақыт күрделілігі) немесе пайдаланатын жад мөлшері (кеңістік күрделілігі) арасындағы байланысты анықтайтын функцияны табуды қамтиды. Алгоритм тиімді деп есептеледі, егер осы функцияның мәндері кішкентай болса немесе кіріс көлемі өскенде олар баяу өссе. Бірдей көлемдегі әртүрлі кірістер алгоритмнің әртүрлі жұмыс істеуіне әкелуі мүмкін, сондықтан ең жақсы, ең нашар және орташа жағдайлар туралы сипаттамалар маңызды болуы мүмкін. Басқаша көрсетілмесе, алгоритмнің өнімділігін сипаттайтын функция әдетте ең нашар жағдайдағы кірістер бойынша анықталған жоғарғы шек болып табылады. "Алгоритмдерді талдау" термині Дональд Кнутпен енгізілген. Алгоритмдерді талдау – есептеу күрделілігі теориясының маңызды бөлігі, ол белгілі бір есептеу мәселесін шешетін кез келген алгоритмге қажетті ресурстардың теориялық бағалауын ұсынады. Бұл бағалаулар тиімді алгоритмдерді іздеудің дұрыс бағыттарын анықтауға көмектеседі. Алгоритмдерді теориялық талдағанда, олардың күрделілігін асимптотикалық тұрғыдан бағалау жиі кездеседі, яғни кез келген үлкен кіріс үшін күрделік функциясын бағалау. Осы мақсатта Big O, Big Omega және Big Theta нотациялары қолданылады. Мысалы, бинарлық іздеу сұрыпталған тізімнің n мөлшерінің логарифміне пропорционалды қадамдар санымен немесе O(log n) – «логарифмдік уақытта» орындалады деп айтуға болады. Асимптотикалық бағалаулар көбінесе қолданылады, өйткені бір алгоритмнің әртүрлі іске асырылуы тиімділік жағынан өзгеше болуы мүмкін. Дегенмен, берілген алгоритмнің екі «ақылға қонымды» іске асырылуының тиімділігі жасырын тұрақты деп аталатын тұрақты көбейткіш фактормен байланысты. Тиімділіктің нақты (асимптотикалық емес) өлшемдерін есептеуге болады, бірақ олар көбінесе алгоритмнің нақты іске асырылуына қатысты белгілі бір болжамдарды, яғни есептеу моделін қажет етеді. Есептеу моделі абстрактілі компьютер, мысалы, Тьюринг машинасы, және/немесе кейбір операциялар бірлік уақытта орындалады деген постулаттар арқылы анықталуы мүмкін. Мысалы, егер біз бинарлық іздеуді қолданатын сұрыпталған тізімде n элемент болса және тізімдегі элементтің әрбір іздеуін бірлік уақытта орындауға кепілдік бере аламыз, онда жауапты қайтару үшін ең көп дегенде log2(n) + 1 уақыт бірлігі қажет болады.

In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the size of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same size may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm. The term "analysis of algorithms" was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms. In theoretical analysis of algorithms it is common to estimate their complexity in the asymptotic sense, i. e., to estimate the complexity function for arbitrarily large input. Big O notation, Big omega notation and Big theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the size n of the sorted list being searched, or in O(log n), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called a hidden constant. Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called model of computation. A model of computation may be defined in terms of an abstract computer, e. g. Turing machine, and/or by postulating that certain operations are executed in unit time. For example, if the sorted list to which we apply binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log2(n) + 1 time units are needed to return an answer.

Орындау уақытын талдау

Жүргізу уақытын талдау – алгоритмнің кіріс мөлшері (әдетте n деп белгіленеді) артқан сайын, оның жұмыс істеу уақытының (немесе орындалу уақытының) өсуін бағалау және болжауға мүмкіндік беретін теориялық жіктеме. Орындалу уақытының тиімділігі – компьютер ғылымында маңызды мәселе: Бағдарламаның орындалуына секундтар, сағаттар, тіпті жылдар қажет болуы мүмкін, бұл қолданылған алгоритмге байланысты. Бағдарламалық профильдеу техникаларын алгоритмнің орындалу уақытын тәжірибеде өлшеу үшін пайдалануға болады, бірақ олар барлық мүмкін кірістер үшін уақыт деректерін қамтамасыз ете алмайды; мұндай деректерді алуға тек жүргізу уақытын талдаудың теориялық әдістері ғана мүмкіндік береді.

Өсу реті

Бейресми түрде, алгоритм математикалық функция ретіндегі өсу деңгейін көрсетеді деп айтуға болады, егер белгілі бір кіріс мөлшері n-ден асып кеткенде, f(n) функциясын оң тұрақтыға көбейту сол алгоритмнің орындалу уақытының жоғарғы шегін немесе лимитін беретін болса. Яғни, белгілі бір n0-ден үлкен n және c тұрақтысы үшін, алгоритмнің орындалу уақыты c × f(n)-нан артық болмайды. Бұл түсінік көбінесе Big O нотациясы арқылы көрсетіледі. Мысалы, енгізу сұрыптау алгоритмінің орындалу уақыты кіріс мөлшері арта келе квадраттық түрде өседі, сондықтан енгізу сұрыптау O(n²) ретінде сипатталады. Big O нотациясы – берілген алгоритм үшін ең нашар жағдайды көрсетудің ыңғайлы тәсілі, бірақ оны орташа жағдайды көрсету үшін де қолдануға болады. Мысалы, жылдам сұрыптау алгоритмінің ең нашар жағдайы O(n²), ал орташа жағдайдағы орындалу уақыты O(n log n).

Өсудің эмпирикалық реті

Егер орындалу уақыты қуат заңына бағынса, t ≈ kn^(a) болса, a коэффициентін кейбір мәселе өлшемдері {n1, n2} үшін орындалу уақытының {t1, t2} эмпирикалық өлшемдерін алып, 1 = t2/t1 = (n2/n1)^(a) есебі арқылы табуға болады, осылайша 1 = a = log(t2/t1)/log(n2/n1). Басқаша айтқанда, бұл орындалу уақытының логарифм-логарифм графигіндегі эмпирикалық түзудің кейбір өлшем нүктесіндегі еңісін өлшейді. Егер өсу реті шын мәнінде қуат заңына бағынса (яғни логарифм-логарифм графигіндегі түзу шын мәнінде түзу болса), эмпирикалық мән әртүрлі диапазондықта тұрақты болады, ал егер бағынбаса, онда өзгереді (және түзу қисық болады) – бірақ бәрібір кез келген екі алгоритмді олардың эмпирикалық жергілікті өсу реті бойынша салыстыруға болады. Жоғарыдағы кестеге қолданылған: n (тізім мөлшері) Компьютер A орындалу уақыты (наносекундтарда) Жергілікті өсу реті (n^ ) Компьютер B орындалу уақыты (наносекундтарда) Жергілікті өсу реті (n^ ) 15 7 100,000 65 32 1.04 150,000 0.28 250 125 1.01 200,000 0.21 1,000 500 1.00 250,000 0.16 1,000,000 500,000 1.00 500,000 0.10 4,000,000 2,000,000 1.00 550,000 0.07 16,000,000 8,000,000 1.00 600,000 0.06 Бірінші алгоритм шын мәнінде қуат заңына бағынатын сызықтық өсу ретін көрсетеді. Екіншісі үшін эмпирикалық мәндер тез төмендеп барады, бұл оның өсудің басқа заңына бағынатынын және кез келген жағдайда өсудің әлдеқайда төмен жергілікті реті бар екенін (және одан да жақсарып жатқанын) эмпирикалық тұрғыдан көрсетеді.

Қатысуы

Алгоритмдік талдау практикада маңызды, себебі тиімсіз алгоритмді кездейсоқ немесе ойсыз пайдалану жүйе жұмысына елеулі әсер ете алады. Уақытқа сезімтал қолданбаларда алгоритмнің орындалуына тым көп уақыт кетсе, оның нәтижелері қарт болып, немесе қолдануға жарамсыз болуы мүмкін. Тиімсіз алгоритм сондай-ақ жұмыс істеу үшін тым көп есептеу қуаты мен жадты қажет етуі мүмкін, осылайша оны іс жүзінде пайдасыз етеді.

Тұрақты факторлар

Алгоритмдерді талдау көбінесе асимптотикалық өнімділікке, әсіресе қарапайым жағдайларда назар аударады, бірақ практикалық қолданыстарда тұрақты коэффициенттер маңызды, ал нақты деректер көлемі әрқашан шектеулі болады. Көлемі әдетте қолжетімді жадтың мөлшерімен шектеледі, сондықтан 32 биттік машиналарда 232 = 4 ГиБ (сегменттелген жад қолданылса, одан да көп) және 64 биттік машиналарда 264 = 16 ЭиБ. Осылайша, шектеулі көлемді ескере отырып, өсу реті (уақыт немесе кеңістік) тұрақты коэффициентпен алмастырылуы мүмкін, және осы тұрғыдан алғанда, барлық практикалық алгоритмдер жеткілікті үлкен тұрақты мән үшін немесе жеткілікті кішкентай деректер үшін O(1) болып табылады. Бұл түсіндіру, ең алдымен, өте баяу өсетін функциялар үшін пайдалы: (бинарлық) итерациялық логарифм (log*) барлық практикалық деректер үшін 5-тен кем; (бинарлық) лог лог (log log n) барлық практикалық деректер үшін 6-дан кем (264 бит); және бинарлық лог (log n) барлық практикалық деректер үшін 64-тен кем (264 бит). Тұрақты емес күрделілікке ие алгоритм, егер тұрақты уақыт алгоритмінің қосымша шығындары үлкен тұрақты коэффициентке әкелсе, практикалық деректерде тұрақты күрделілікке ие алгоритмге қарағанда тиімдірек болуы мүмкін, мысалы, болуы мүмкін, егер және болса. Үлкен деректер үшін сызықтық немесе квадраттық коэффициенттерді елемеуге болмайды, бірақ кішкентай деректер үшін асимптотикалық тұрғыдан тиімсіз алгоритм тиімдірек болуы мүмкін. Бұл әсіресе гибридті алгоритмдерде қолданылады, мысалы, Timsort, ол асимптотикалық тұрғыдан тиімді алгоритмді (осы жерде біріктіру сұрыптау, уақыт күрделілігімен ) пайдаланады, бірақ кішкентай деректер үшін асимптотикалық тұрғыдан тиімсіз алгоритмға (осы жерде енгізу сұрыптау, уақыт күрделілігімен ) ауысады, себебі қарапайым алгоритм кішкентай деректерде жылдамырақ жұмыс істейді.