In mijn algoritme en data structures klasse kregen we een paar recidiefrelaties om op te lossen of dat we de complexiteit van een algoritme kunnen zien.
In eerste instantie dacht ik dat het doel van deze relaties is om de complexiteit van een recursief verdeling-en-veroverd algoritme te noteren. Toen kwam ik een vraag over in de MIT-opdrachten, waar men wordt gevraagd om een herhaling te bieden voor een iteratief algoritme.
Hoe zou ik mezelf eigenlijk met een recidief-relatie komen, wat een code heeft gegeven? Wat zijn de benodigde stappen?
is het eigenlijk corrigeren dat ik op elk geval I.E. Slechtste, beste, gemiddelde behuizing met zo’n relatie kan doen?
kan mogelijk iemand een eenvoudig voorbeeld geven over hoe een stuk code wordt veranderd in een recidiefrelatie?
gejuich,
Andrew
Antwoord 1, Autoriteit 100%
Oké, dus in algoritme-analyse is een herhalingrelatie een functie die de hoeveelheid werk betreft die nodig is om een probleem van grootte N op te lossen, die nodig is om kleinere problemen op te lossen (dit is nauw verwant aan de betekenis van de betekenis in wiskunde).
Overweeg bijvoorbeeld een FIBONACCI-functie hieronder:
Fib(a)
{
if(a==1 || a==0)
return 1;
return Fib(a-1) + Fib(a-2);
}
Dit voert drie bewerkingen uit (vergelijking, vergelijking, optelling) en noemt zichzelf ook recursief. Dus de herhalingsrelatie is T(n) = 3 + T(n-1) + T(n-2). Om dit op te lossen, zou je de iteratieve methode gebruiken: begin de termen uit te breiden totdat je het patroon vindt. Voor dit voorbeeld zou je T(n-1)uitbreiden om T(n) = 6 + 2*T(n-2) + T(n-3). Breid vervolgens T(n-2)uit om T(n) = 12 + 3*T(n-3) + 2*T(n-4)te krijgen. Breid nog een keer T(n-3)uit om T(n) = 21 + 5*T(n-4) + 3*T(n-5). Merk op dat de coëfficiënt van de eerste T-term de Fibonacci-getallen volgt, en de constante term is de som van hen maal drie: zoek het op, dat is 3*(Fib(n+2)-1). Belangrijker is dat we merken dat de reeks exponentieel toeneemt; dat wil zeggen, de complexiteit van het algoritme is O(2n).
Overweeg dan deze functie voor merge sort:
Merge(ary)
{
ary_start = Merge(ary[0:n/2]);
ary_end = Merge(ary[n/2:n]);
return MergeArrays(ary_start, ary_end);
}
Deze functie roept zichzelf twee keer aan op de helft van de invoer en voegt vervolgens de twee helften samen (met behulp van O(n) werk). Dat wil zeggen, T(n) = T(n/2) + T(n/2) + O(n). Om herhalingsrelaties van dit type op te lossen, moet je de Hoofdstellinggebruiken. Volgens deze stelling wordt dit uitgebreid tot T(n) = O(n log n).
Overweeg ten slotte deze functie om Fibonacci te berekenen:
Fib2(n)
{
two = one = 1;
for(i from 2 to n)
{
temp = two + one;
one = two;
two = temp;
}
return two;
}
Deze functie noemt zichzelf no times, en itereert O(n) times. Daarom is de herhalingsrelatie T(n) = O(n). Dit is het geval waar u naar vroeg. Het is een speciaal geval van herhalingsrelaties zonder herhaling; daarom is het heel gemakkelijk op te lossen.
Antwoord 2, autoriteit 19%
Om de looptijd van een algoritme te vinden, moeten we eerst een uitdrukking voor het algoritme kunnen schrijven en die uitdrukking vertelt de looptijd voor elke stap. U moet dus elk van de stappen van een algoritme doorlopen om de uitdrukking te vinden.
Stel dat we een predikaat hebben gedefinieerd, isSorted, dat als invoer een array a en de grootte, n, van de array zou nemen en true zou retourneren als en alleen als de array in oplopende volgorde was gesorteerd.
bool isSorted(int *a, int n) {
if (n == 1)
return true; // a 1-element array is always sorted
for (int i = 0; i < n-1; i++) {
if (a[i] > a[i+1]) // found two adjacent elements out of order
return false;
}
return true; // everything's in sorted order
}
Het is duidelijk dat de grootte van de invoer hier gewoon n is, de grootte van de array. Hoeveel stappen worden er in het ergste geval uitgevoerd voor invoer n?
De eerste if-instructie telt als 1 stap
De for-lus wordt in het ergste geval n−1 keer uitgevoerd (ervan uitgaande dat de interne test ons er niet uitgooit), voor een totale tijd van n−1 voor de lustest en de verhoging van de index .
Binnen de lus is er nog een if-statement dat één keer per iteratie wordt uitgevoerd, in het slechtste geval n−1 keer.
De laatste aangifte wordt één keer uitgevoerd.
Dus in het ergste geval hebben we 1+(n−1)+(n−1)+1 gedaan
Berekeningen, voor een totale looptijd T (n) ≤1 + (N-1) + (N-1) + 1 = 2N en dus hebben we de timingfunctie T (n) = O (n).
Dus in het kort wat we hebben gedaan is – & GT; & GT;
1.Voor een parameter ‘n’ die de omvang van de ingang geeft die we aannemen dat elke eenvoudige verklaringen die eenmaal worden uitgevoerd, een constante tijd zullen nemen, voor eenvoud aannemende een
2.De iteratieve uitspraken zoals lussen en in het lichaam zullen variabele tijd nemen, afhankelijk van de invoer.
Welke oplossing t (n) = o (n), net als bij de niet-recursieve versie, zoals het gebeurt.
3. Dus uw taak is om stap voor stap te gaan en de functie op te schrijven in termen van n om de tijdcomplexiteit
te caluleren
Voor recursieve algoritmen, doe je hetzelfde, alleen deze keer voegt u de tijd toe die wordt genomen door elke recursieve oproep, uitgedrukt als een functie van de tijd die het inputeert.
Laten we bijvoorbeeld herschrijven, gunstig zijn als een recursief algoritme:
bool isSorted(int *a, int n) {
if (n == 1)
return true;
if (a[n-2] > a[n-1]) // are the last two elements out of order?
return false;
else
return isSorted(a, n-1); // is the initial part of the array sorted?
}
In dit geval lopen we nog steeds door het algoritme, tellen: 1 stap voor de eerste als plus 1-stap voor de tweede indien, plus het gedetailleerde tijdsomstandigheden, dat een input van grootte N-1 zal opleveren, wat t (n -1), het geven van een recidiefrelatie
T (n) ≤1 + 1 + T (N-1) = t (N-1) + O (1)
die oplossing heeft t (n) = O (n), net als bij de niet-recursieve versie, zoals het gebeurt.
eenvoudig genoeg !! Oefen meer om de recidiefrelatie van verschillende algoritmen te schrijven, rekening houdend met hoeveel tijd elke stap wordt uitgevoerd in algoritme