Int f(int x) { if (x==0) return 0; else return (2*f(x-1)+x*x)

voidDoubleCountDown (int N)

{ if(N<=0);

{DoubleCountDown(N-1); DoubleCountDown(N-1)}

/*времето се удвоява ???
нека имаме означението Т(N) и Т(0)=1; времето на изпълнение се подчинява на формулата:1+2Т(N-1)

N 0 1 2 3 4 10

T(N) 1 3 7 15 31 2047
виждаме Т(N) = 2^N+1 – 1->O(2^N)
Може също да се получи и индиректна рекурсия:пр. Криви на Шерпшински О(4^N). При това се получава разход на памет:

Int BadForMemory()

{ int *x; GetMemory(x,10 000); BadForMemory(); }
Съществуват техники на формално преобразуване на рекурс в нерекурс алг.
2)Запаметяване на междинни резултати :

1)Премахване на опашна рекурсия

procedure Recurse(A: Integer); begin

//извършва нещо

Recurse(B) end;

procedure NonRecurse(A: Integer) begin

while(not done) do begin

//извършва нещо

A:=B;

end; end ;

пр.: Fibonacci числа: за Fib(29)-> Fib(1) и Fib(0) се изчисляват 832 040 пъти??? Междинните резултати се съхраняват в таблица след първото изчисляване.

3. 
   Подменяне посоката top-down към botton-up(пр. с Fibonacci числа)
   

При тази техника оценката за алг.на Fibonacci е О(N) за Fib(N) вместо O(Fib(N))
Напр. за Pentium 166 MHz и Fib(40) 155 sec с рекурсивен алгоритъм,докато с тази модификация Fib(1476) се смята за

3. 
   Подмяна на алг.чрез преструктуриране на кода:оформяне процеса за съхраняване на информацията,стъпка и възстановяване:
   

Изтегляне 1.47 Mb.

Сподели с приятели: