5. Анализ на сложността на рекурсивните алгоритми
Разгледайте първо случая на директна рекурсия с едно (извън всеки цикъл) рекурсивно извикване в тялото на процедурата. Пример за такъв алгоритъм е алгоритъмът на Евклид за изчисляване на най-голям общ делител. Текстът на рекурсивната процедура с вектора на входните данни X съдържа извикване на същата процедура с вектора на входните данни Y = f(X), променен по някакво правило. В допълнение, текстът съдържа някои нерекурсивни изчисления h(X) и операции за сравнение c(X,S) на стойността на X със стойността на S, при която рекурсивният процес трябва да приключи. Нека обозначим "точната" (а не горната граница или средната) стойност на сложността, дадена на входните данни X като Ta(X). Тогава
Ta(X) = Ta(Y)+Th(X)+Tc(X,S) или Ta(X) = Ta(AX))+Tf(X)+Th(X)+ Tc(X,S).
Второто отношение е рекурентно уравнение за определяне на стойностите на неизвестната функция Ta(X) чрез известните стойности f(A), Tf(X), Th(X), Tc(X,S). Освен това има начално условие Ta(S)=Ts(S) с известна функция на сложността на изчисляване на (нерекурсивната) стойност S. По този начин има система:
Ta(X)=Ta(f(X))+ Tf(X)+Th(X)+ Tc(X, S)a(S)=Tc(S,S)+Ts(S)
Това е частен случай на рекурсивно уравнение. Такива уравнения имат развита теория. В някои случаи е възможно аналитично решение. Нека покажем приложението му на примера на рекурсивно факторно изчисление:
функция ФАКТОРИАЛ(x: цяло число): цяло число;x = 1 след това ФАКТОРИАЛ:= 1ФАКТОРИАЛ:= x * ФАКТОРИАЛ(x-1);;
Тук X=x, S=1, f(X)=X-1, Tf(X)=1, Th(X) = 2, Tc(X,S)=l, Ts(S) = 1. Така системата от уравнения се превръща в Ta(x) = Ta(x-1)+4, Ta(1) = 2. Нейното решение е Ta(x) = 4x-2.
Горната граница Ta(V) може да бъде получена по подобен начин, но с помощта на рекурсивни неравенства:
Ta(V) f(средно(X)), с изключение на случаялинейна функция f.
Сега разгледайте по-общия случай на директна рекурсия (4, стр. 402-404) с множество рекурсивни извиквания в тялото на процедурата. Тези извиквания могат да имат различни аргументи Y1, Y2, . . . ,Yk, където Y1 =fl(X), Y2 =f2(X), . Yk=fk(X). Рекурентното уравнение за функцията на сложност има формата
Ta(X) = Ta(f1(X)) + Ta(f2(X)) + . + Ta(fk(X)) + Tf1(X) + Tf2(X) + . +Tfk(X) + Th(X) + Tc(X, S)
Taa(S) = Tc(S, S) + Ts(S).
6. Оптимизация на алгоритъма
Досега компютърните науки не са натрупали достатъчно информация, така че проблемът за минимизиране да може да бъде поставен с обичайната за математиката сигурност. Няколко фактора пречат на това.
Първо, трудно е да се формулира критерий за оптимизация, който да има както неоспоримо практическо значение, така и недвусмислено дефиниран математически. Например, може да се постави задача за минимизиране на броя инструкции на машина на Тюринг, критерий, добре дефиниран математически; но практическото му значение изобщо не е ясно, тъй като е малко вероятно истинска програма на истински компютър да симулира машина на Тюринг. Може да се постави задача за минимизиране на времето за изпълнение на програма на реална машина - критерий, който е ясен от практическа гледна точка. Въпреки това ще бъде невъзможно да се реши проблемът с оптимизацията чрез математически методи, тъй като времето за изпълнение зависи (понякога значително) от компютърната архитектура, а архитектурата на съвременните компютри не може да бъде описана с малък брой параметри. Също така е важно, че програма, която работи по-бързо от други на един компютър, може да не е най-бързата на друг. Има дори специални програми, наречени "бенчмарк", предназначени за оценка на архитектури.
Второ, не е съвсем ясно каква е сложността на задачата. Може да се определи като минимум отсложността на алгоритмите, които решават този проблем. Но съществува ли алгоритъм с минимална сложност (как да се уверим, че намереният алгоритъм наистина е минимален или, обратно, не е минимален)? Има ли към какво да се стремим? И колко трудно е търсенето на този минимум? Тези въпроси са свързани с долната граница на сложността на алгоритмите (а не с горната граница, както в предишните стъпки) (5, стр. 89-92).
Възможно ли е да се докаже за разглеждания проблем, че никой алгоритъм, който го решава, не може да бъде по-прост от тази долна граница? Вземете добре известната задача за умножение на квадратна матрица. Даден е алгоритъм със сложност Ta(n) = 3n3 + n2. (8, стр. 199-203) Това вероятно не е най-добрият алгоритъм, но каква е по-ниската оценка? Получената матрица има n2 елемента. За да се изчисли всеки елемент, е необходима поне една операция на еднопроцесорна машина - два елемента не могат да бъдат намерени в една операция. За минималния алгоритъм получаваме неравенствата n2
Съответното уравнение (едно от възможните) е >
Методът за разделяне на задача на подзадачи.
Вторият тип оптимизация, без да променя структурата на програмата като цяло, води до спестяване на памет и/или опростяване на работата със структури от данни, повишаване на ефективността на спомагателните процедури, които осигуряват "интерфейс" между нивото на приложението (на което мислим от гледна точка на обекти от високо ниво - графики, матрици, текстове и т.н.) и нивото на машината, което поддържа най-простите типове данни (числа, символи, указатели). Резултатът от това обикновено е намаляване на коефициентите при някои членове на функцията за сложност (при успешна оптимизация - при най-значимия член), но редът на функцията за сложност остава същият. (7, стр. 204)
И двата вида оптимизация се допълват взаимно и могат да се използват заедно.