Big Oh ved rekursjon

[V_B]

Hei.

 

Jeg sliter litt med tankegangen rundt Big Oh kjøretider når det er rekursjon i bildet. Jeg klarer ikke helt å samle tankene på hvordan jeg skal sette opp tidsfunksjonen? Her kommer et enkelt og greit eksempel

 

 

Hvordan setter man opp kjøretiden for metoden "fac"? Er det så enkelt at man bare kan tenke at man gjør "n" antall kall, og at multiplikasjonen med "n" anses som en enkel operasjon? Eller anser vi dette som n^2 operasjoner?

 

Takk!

[Matsemann]

Å gange noe kan en her se på som O(1). Dette gjøres n ganger, altså O(n*1) blir O(n).

 

Når en jobber med rekursjon bør en se hvor mange nye funksjonskall som lages i hvert funksjonskall, samt hvor mye arbeid som gjøres. F. eks. vil

public int something(int x) {
   // if (en eller annen base-case) ... else {
   return something(x-1) * something(x-2);
}

Første være 1, som vil lage 2 nye, som hver vil lage 2 nye kall osv.

 

Se på master-teoremet, gjør at man i hovedsak bare trenger å lære seg 3 forskjellige cases av rekursjon, så kan en regne ut O-notasjon for det meste.

[V_B]

Aha, skal søke det opp! Takk for veiledning og hjelp!