yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы структуры данных

Вызовы процедур.

Для программ, содержащих несколько процедур (среди которых нет рекурсивных), можно подсчитать общее время выполнения программы путем последовательного нахождения времени выполнения процедур, начиная с той, которая не имеет вызовов других процедур. (Вызов процедур мы определяем по наличию оператора call.) Так как мы предположили, что все процедуры нерекурсивные, то должна существовать хотя бы одна процедура, не имеющая вызовов других процедур. Затем можно определить время выполнения процедур, вызывающих эту процедуру, используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этот процесс, найдем время выполнения всех процедур и, наконец, время выполнения всей программы.

Если есть рекурсивные процедуры, то нельзя упорядочить все процедуры таким образом, чтобы каждая процедура вызывала только процедуры, время выполнения которых подсчитано на предыдущем шаге. В этом случае мы должны с каждой рекурсивной процедурой связать временную функцию Т(п), где п определяет объем аргументов процедуры. Затем мы должны получить рекуррентное соотношение для Т(п), т.е. уравнение (или неравенство) для Т(п), где участвуют значения T(k) для различных значений k.

Техника решения рекуррентных соотношений зависит от вида этих соотношений, некоторые приемы их решения будут показаны в теме 9. Сейчас же мы проанализируем простую рекурсивную программу.

Пример 1.10. В листинге 1.5 представлена программа вычисления факториала n!, т.е. вычисления произведения целых чисел от 1 до п включительно.

Листинг 1. 5.

function  fact   (  n:   integer  ) :   integer;

fact(n)   вычисляет n!   }

begin

(1)       if   n   <=   1   then                                              

(2)            fact:=   1                                         

else

(3)            fact:- n * fact(n - 1)

end;   {  fact }

Естественной мерой объема входных данных для функции fact является значение п. Обозначим через Т(п) время выполнения программы. Время выполнения для строк(1) и (2) имеет порядок О(1), а для строки (3) — О(1) + Т(п - 1). Таким образом, для некоторых констант c и d имеем

                                  T(n)=      c+ T(n-1),       если n>1,      

d,                    если n ≤ 1.                                                     (1.1)

Полагая, что п > 2, и раскрывая в соответствии с соотношением (1.1) выражение Т(п - 1) (т.е. подставляя в (1.1) п - 1 вместо n), получим Т(п) = 2с + Т(п - 2). Аналогично, если п > 3, раскрывая Т(п - 2), получим Т(п) - 3с + Т(п - 3). Продолжая этот процесс, в общем случае для некоторого і, п > і, имеем Т(п) = іс + Т(п - і). Положив в последнем выражении і = n - 1, окончательно получаем

Т(п) = с(п - 1) + T(1) = с(п - 1) + d,                                         (1.2)

Из (1.2) следует, что Т(п) имеет порядок О(п). Отметим, что в этом примере анализа программы мы предполагали, что операция перемножения двух целых чисел имеет порядок О(1). На практике, однако, программу, представленную в листинге 1.5, нельзя использовать для вычисления факториала при больших значений n, так как размер получаемых в процессе вычисления целых чисел может превышать длину машинного слова.

Общий метод решения рекуррентных соотношений, подобных соотношению из примера 1.10, состоит в последовательном раскрытии выражений T(k) в правой части уравнения (путем подстановки в исходное соотношение k вместо п) до тех пор, пока не получится формула, у которой в правой части отсутствует Т (как в формуле (1.2)). При этом часто приходится находить суммы различных последовательностей; если значения таких сумм нельзя вычислить точно, то для сумм находятся верхние границы, что позволяет, в свою очередь, получить верхние границы для Т(п).

 

 

13