Tijdscomplexiteit

[Lgamer]

Weet iemand hoe je de tijdscomplexiteit van volgende broncode kan bepalen? Ik snap er namelijk niets van.

public int fibonacciRecursief(int n)
{
if(n == 1 || n == 2) return 1;
else{ return fibonacciRecursief(n-2) +
fibonacciRecursief(n-1); }

We begonnen algemeen maar zijn dan overgeschakeld naar het definiëren van een "minimum-" en "maximum-complexiteit". We bekwamen dat de complexiteit exponentieel is, nl. 2^n.

 

[kenikavanbis]

Kan je iets duidelijker willen zijn wil je de run time weten dan zal je moeten rekening houden met max. grote van int en die is verandert dus ... en dan moet je weten welke op welk systeem je het draait.

 

[bmtvrr]

Hoewel de naam anders doet vermoeden is de tijdscomplexiteit van een algoritme niet de tijd die het nodig heeft om een probleem op te lossen, maar het aantal stappen dat het moet zetten om om tot een oplossing te komen, tenminste dat is wat er op wikipedia staat:

Het aantal benodigde stappen om tot een oplossing van het probleem te komen, is de tijdscomplexiteit van het probleem.

 

[kenikavanbis]

met een variabele buiten de loop en een ++ moet dat dan toch wel lukken zou ik denken