Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
Типове рекурсия и оценки:А) премахва 1 елемент от N входящи числа при циклично прохождане Cn=Cn-1+N; C1=1 Док: Cn=Cn+1+N=Cn-2+(N-1)+N= C1.. +2+..N=1+2+…+(N-2)+(N-1)+N= =[N(N+1)]/2.=>Cn≈N2/2 Б)рекурсии с разполовяване на входния поток на всяка стъпка Cn=2Cn/2+1 ; C1=1; 2 2 2 2 Док:некаN=2n(пр.битове за предст.на N)=> C n=C n-1+1= C n-2+1+1= C n-3+3= 2 …=C 0+n=n+1 => Оптимизации при взаимна рекурсия + малко от горния въпросоценката на CN зависи от броя битове, необходими за представяне на N-> lgN В)рекурсивни програми,разполовяващи входа,но преглеждащи всеки елемент Cn=Cn/2+N; C1=0 ; Док: разписва се като N+N/2+N/4+N/8+… =>Оценката е строго пропорц.на вх.->2N Г)рекурсии с лин.обхождане на входа преди,по време или след разполов.на входа Cn=2Cn/2+N;C1=0(алг.“разделяй и владей”) 2 2 Док: C n=2C n-1+2n ; делим на2 2 2 2 2 N ->: C n/2n=[C n-1/2n-1]+1=[2C n-2+2n-1]/2n-1+1 =C n-2/2n-2+2=…=n ->C =NlgN Рекурсивен алгоритъм е този, който решава проблем чрез решаването на един или по-малки екземпляри на същия проблем.За да реализираме рекурсивни алг, използваме рекурсивни функции-рекурсивна функция е тази,която вика себе си.Рекурентни връзки са рекурсивно дефинирани функции. Една рекурентна връзка дефинира функция,чиято деф. област е неотрицателните цели числа или чрез някакви начални стойнос-ти,или (рекурентно) от гледна точка на нейни собствени стойности върху по-малки цели числа.Може би най-известната такава функция е функцията факториел,която се декларира чрез рекурентната връзка N!=N(N-1)! , за N>=1, 0!=1. Ние използваме рекурсия,защото тя често ни помага да изразим сложни алг в компактна форма,без да жертваме ефикасност.Но както се оказва много лесно е да напишем проста рекурсивна фунция,която е изключително неефективна и е необх да упражняваме грижата да избягваме да бъдем натоварени с труднообработваеми реализации.Ето пример за една рекурсия: Изтегляне 1.47 Mb. Сподели с приятели:
|