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)Запаметяване на междинни резултати :
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 пъти??? Междинните резултати се съхраняват в таблица след първото изчисляване.
Подменяне посоката top-down към botton-up(пр. с Fibonacci числа)
При тази техника оценката за алг.на Fibonacci е О(N) за Fib(N) вместо O(Fib(N))
Напр. за Pentium 166 MHz и Fib(40) 155
sec с рекурсивен алгоритъм,докато с тази модификация Fib(1476) се
смята за
Подмяна на алг.чрез преструктуриране на кода:оформяне процеса за съхраняване на информацията,стъпка и възстановяване:
Сподели с приятели: